Cover Image

On Computing Vertex Connectivity of 1-Plane Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Biedl, Therese, Murali, Karthik
Format:	Preprint
Published:	2022
Subjects:	Computational Geometry Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
by: Biedl, Therese, et al.
Published: (2024)

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
by: Biedl, Therese
Published: (2025)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
by: Biedl, Therese, et al.
Published: (2026)

Finding maximum matchings in RDV graphs efficiently
by: Biedl, Therese, et al.
Published: (2024)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
by: Filtser, Arnold
Published: (2024)

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
by: Galby, Esther, et al.
Published: (2023)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
by: Cabello, Sergio, et al.
Published: (2025)

Zone Theorem for Arrangements in three dimensions
by: Saxena, Sanjeev
Published: (2020)

O(1)-Distortion Planar Emulators for String Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Computing Subset Vertex Covers in $H$-Free Graphs
by: Brettell, Nick, et al.
Published: (2023)

Dynamic Connectivity in Disk Graphs
by: Baumann, Alexander, et al.
Published: (2021)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)

Approximately: Independence Implies Vertex Cover
by: Har-Peled, Sariel
Published: (2023)

The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability
by: Feghali, Carl, et al.
Published: (2025)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
by: Le, Hoang-Oanh, et al.
Published: (2024)

Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
by: Klemz, Boris, et al.
Published: (2024)

Maximizing Weighted Dominance in the Plane
by: Akram, Waseem, et al.
Published: (2024)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\ell)$-Sparse Subgraphs
by: Madarasi, Péter
Published: (2025)

Implicit representations via the polynomial method
by: Cardinal, Jean, et al.
Published: (2026)

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
by: Gribanov, D., et al.
Published: (2023)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
by: Deák, Bence, et al.
Published: (2025)

Computing Maximum Cliques in Unit Disk Graphs
by: Tkachenko, Anastasiia, et al.
Published: (2025)

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

Minimum-Weight Half-Plane Hitting Set
by: Liu, Gang, et al.
Published: (2025)

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
by: Banik, Aritra, et al.
Published: (2025)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
by: Chan, Timothy M., et al.
Published: (2026)

Connected Partitions via Connected Dominating Sets
by: Niklanovits, Aikaterini, et al.
Published: (2025)

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
by: Spalding-Jamieson, Jack
Published: (2025)

Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
by: Hougardy, Stefan, et al.
Published: (2024)

The Squishy Grid Problem
by: Cai, Zixi, et al.
Published: (2025)

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
by: Conradi, Jacobus, et al.
Published: (2026)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
by: Beisegel, Jesse, et al.
Published: (2025)

On $[1,2]$-Domination in Interval and Circle Graphs
by: Meybodi, Mohsen Alambardar, et al.
Published: (2024)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
by: Dakhno, Grigorii, et al.
Published: (2024)

Ghost Value Augmentation for $k$-Edge-Connectivity
by: Hershkowitz, D Ellis, et al.
Published: (2023)