Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
From MaRDI portal
Publication:5396947
DOI10.1137/120872310zbMath1282.05033arXiv1203.5944OpenAlexW2964235807WikidataQ57255586 ScholiaQ57255586MaRDI QIDQ5396947
Publication date: 4 February 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1203.5944
Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (43)
Outer 1-planar graphs ⋮ Recognizing and drawing IC-planar graphs ⋮ Straight-Line Drawability of a Planar Graph Plus an Edge ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ There are no cubic graphs on 26 vertices with crossing number 10 or 11 ⋮ Parameterized analysis and crossing minimization problems ⋮ On quasi-planar graphs: clique-width and logical description ⋮ An annotated bibliography on 1-planarity ⋮ Deciding Parity of Graph Crossing Number ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ The book thickness of 1-planar graphs is constant ⋮ \(\mathsf{NIC}\)-planar graphs ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Inapproximability ratios for crossing number ⋮ A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system ⋮ Six variations on a theme: almost planar graphs ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Weak-dynamic coloring of graphs beyond-planarity ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ Extending simple drawings ⋮ Exact crossing number parameterized by vertex cover ⋮ Rotation and crossing numbers for join products ⋮ On the \(k\)-planar local crossing number ⋮ Complexity of Geometric k-Planarity for Fixed k ⋮ Crossing minimization in perturbed drawings ⋮ A linear-time algorithm for testing outer-1-planarity ⋮ Crossing minimization in perturbed drawings ⋮ A tighter insertion-based approximation of the crossing number ⋮ Unnamed Item ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ Inserting an edge into a geometric embedding ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ Inserting one edge into a simple drawing is hard ⋮ ON THE CROSSING NUMBER OF THE CARTESIAN PRODUCT OF A SUNLET GRAPH AND A STAR GRAPH ⋮ Approximating the Maximum Rectilinear Crossing Number ⋮ Connecting the dots (with minimum crossings) ⋮ Beyond Planar Graphs: Introduction ⋮ Quantitative Restrictions on Crossing Patterns ⋮ Algorithms for 1-Planar Graphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ An effective crossing minimisation heuristic based on star insertion ⋮ 1-planarity testing and embedding: an experimental study ⋮ A Tipping Point for the Planarity of Small and Medium Sized Graphs
This page was built for publication: Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
