On the Cutting Edge: Simplified O(n) Planarity by Edge Addition

DOI10.7155/jgaa.00091zbMath1086.05067WikidataQ56059586 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

zbMATH Keywords

planar embedding; path traversal process

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

Related Items

Improved bounds for hypohamiltonian graphs, Verification of the Jones unknot conjecture up to 22 crossings, An algorithm for an 𝓁²-homological test for the planarity of a graph, Unnamed Item, Quantitative Restrictions on Crossing Patterns, $$\textit{\textbf{k}}$$-Planar Graphs, Revising the Fellows-Kaschube $K_{3,3}$ Search, The Optimal Packing of Eight Points in the Real Projective Plane, Graphs with few hamiltonian cycles, A Linear-Time Algorithm for Finding Induced Planar Subgraphs, Planarity Algorithms via PQ-Trees (Extended Abstract), Cyclic Level Planarity Testing and Embedding, Efficient Extraction of Multiple Kuratowski Subdivisions, Optimality program in segment and string graphs, Acyclic 3-coloring of generalized Petersen graphs, Tractable minor-free generalization of planar zero-field Ising models, Classical vs quantum satisfiability in linear constraint systems modulo an integer, An annotated review on graph drawing and its applications, Grid recognition: classical and parameterized computational perspectives, On protein structure alignment under distance constraint, Invariants of graph drawings in the plane, A branch-and-cut approach to the crossing number problem, Non-planar core reduction of graphs, Linear-time recognition of map graphs with outerplanar witness, A large set of torus obstructions and how they were discovered, On the \(k\)-planar local crossing number, Testing gap \(k\)-planarity is NP-complete, House of graphs 2.0: a database of interesting graphs and more, Switching 3-edge-colorings of cubic graphs, Treetopes and their graphs, Small \(k\)-pyramids and the complexity of determining \(k\), Some results on point visibility graphs, Regularity and planarity of token graphs, Characterizing 2-crossing-critical graphs, Property testing of planarity in the \textsf{CONGEST} model, \((k,p)\)-planarity: a relaxation of hybrid planarity, Recursive computation of Feynman periods, Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem, Communicability Angle and the Spatial Efficiency of Networks, REOPTIMIZATION UNDER VERTEX INSERTION: MAX P_k-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH, A Note on the Practicality of Maximal Planar Subgraph Algorithms, Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs, A New Approach to Exact Crossing Minimization