On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
From MaRDI portal
Publication:3378497
DOI10.7155/jgaa.00091zbMath1086.05067OpenAlexW2121655825WikidataQ56059586 ScholiaQ56059586MaRDI QIDQ3378497
John M. Boyer, Wendy J. Myrvold
Publication date: 3 April 2006
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/52300
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
Related Items
Regularity and planarity of token graphs ⋮ Switching 3-edge-colorings of cubic graphs ⋮ Characterizing 2-crossing-critical graphs ⋮ Planarity Algorithms via PQ-Trees (Extended Abstract) ⋮ Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs ⋮ Linear-time recognition of map graphs with outerplanar witness ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Revising the Fellows-Kaschube $K_{3,3}$ Search ⋮ \((k,p)\)-planarity: a relaxation of hybrid planarity ⋮ The Optimal Packing of Eight Points in the Real Projective Plane ⋮ Recursive computation of Feynman periods ⋮ An annotated review on graph drawing and its applications ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ A Note on the Practicality of Maximal Planar Subgraph Algorithms ⋮ Treetopes and their graphs ⋮ A large set of torus obstructions and how they were discovered ⋮ Improved bounds for hypohamiltonian graphs ⋮ Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs ⋮ A New Approach to Exact Crossing Minimization ⋮ On the \(k\)-planar local crossing number ⋮ Verification of the Jones unknot conjecture up to 22 crossings ⋮ A branch-and-cut approach to the crossing number problem ⋮ Small \(k\)-pyramids and the complexity of determining \(k\) ⋮ On protein structure alignment under distance constraint ⋮ Optimality program in segment and string graphs ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ Cyclic Level Planarity Testing and Embedding ⋮ Efficient Extraction of Multiple Kuratowski Subdivisions ⋮ Acyclic 3-coloring of generalized Petersen graphs ⋮ An algorithm for an 𝓁2-homological test for the planarity of a graph ⋮ Graphs with few hamiltonian cycles ⋮ Non-planar core reduction of graphs ⋮ Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem ⋮ Communicability Angle and the Spatial Efficiency of Networks ⋮ Unnamed Item ⋮ Invariants of graph drawings in the plane ⋮ REOPTIMIZATION UNDER VERTEX INSERTION: MAX Pk-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH ⋮ Quantitative Restrictions on Crossing Patterns ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ Tractable minor-free generalization of planar zero-field Ising models ⋮ Some results on point visibility graphs ⋮ House of graphs 2.0: a database of interesting graphs and more ⋮ Classical vs quantum satisfiability in linear constraint systems modulo an integer ⋮ A Linear-Time Algorithm for Finding Induced Planar Subgraphs
