On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
From MaRDI portal
Publication:3378497
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
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, 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, On protein structure alignment under distance constraint, 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, 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, Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem, Communicability Angle and the Spatial Efficiency of Networks, REOPTIMIZATION UNDER VERTEX INSERTION: MAX Pk-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