Efficient Planarity Testing

Cited in

(only showing first 100 items - show all)

Algorithms for Drawing Planar p-petal Graphs
Computational study on a PTAS for planar dominating set problem
On Boolean characterizations of planarity and planar embeddings of graphs
Planarity algorithms via PQ-trees (extended abstract)
Upward planar morphs
Upward planarity testing in practice: SAT formulations and comparative study
A very personal reminiscence on the problem of computational complexity
Graphs with no \(K_{3,3}\) minor containing a fixed edge
Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks
Efficient Extraction of Multiple Kuratowski Subdivisions
A large set of torus obstructions and how they were discovered
Planarity testing revisited
Simple planar graph partition into three forests
Planarity testing in parallel
An algorithm for reliability analysis of planar graphs
A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas-Eddy class
Facilities layout generalized model solved by n-boundary shortest path heuristics
A simulated annealing algorithm for determining the thickness of a graph
Parameterized complexity of the spanning tree congestion problem
Data Structures and their Planar Graph Layouts
Searching forK_3,3in linear time
Gap strings and spanning forests for bridge graphs of biconnected graphs
Limits of greedy approximation algorithms for the maximum planar subgraph problem
A simulated annealing algorithm for the maximum planar subgraph problem
An algebra for pomsets.
HV-planarity: algorithms and complexity
Computing the flip distance between triangulations
The optimal packing of eight points in the real projective plane
Matching and spanning in certain planar graphs
Linear-time recognition of map graphs with outerplanar witness
Computing k-modal embeddings of planar digraphs
Optimizing concurrency under Scheduling by Edge Reversal
Determining outerplanarity using segment graphs
\(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
scientific article; zbMATH DE number 7651152 (Why is no real title available?)
Dynamic planar embeddings of dynamic graphs
The complexity of finding minimal Voronoi covers with applications to machine learning
Force-directed layout of order diagrams using dimensional reduction
Finding the closed partition of a planar graph
Rikudo is NP-complete
Approximation algorithms for polynomial-expansion and low-density graphs
\((k,p)\)-planarity: a relaxation of hybrid planarity
Analogies between the crossing number and the tangle crossing number
Projective plan and Möbius band obstructions
Compact distributed certification of planar graphs
Some problems in topological graph theory
A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks
Checking the convexity of polytopes and the planarity of subdivisions (extended abstract)
A method of graph reduction and its applications
Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
On universal positive graphs
A direct proof of the strong Hanani-Tutte theorem on the projective plane
The thickness of a minor-excluded class of graphs
Coloring algorithms for \(K_ 5\)-minor free graphs
Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
Approximating the rectilinear crossing number
Planar lattices are lexicographically shellable
Indexing graph search trees and applications
A simple recognition of maximal planar graphs
The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
On the construction of planar embedding for a class of orthogonal polyhedra
A tight lower bound for vertex planarization on graphs of bounded treewidth
Simpler algorithms for testing two-page book embedding of partitioned graphs
scientific article; zbMATH DE number 7662167 (Why is no real title available?)
The QuaSEFE problem
A Note on the Minimum H-Subgraph Edge Deletion
The existence of homeomorphic subgraphs in chordal graphs
Enumeration of articulation pairs of a planar graph
On counting planar embeddings
A simple algorithm for 4-coloring 3-colorable planar graphs
Every triangle-free planar graph has a planar upward drawing
Line directionality of orders
SPLITTING NUMBER is NP-complete
Counting cliques in 1-planar graphs
Nonabelian flows in networks
Graph graphics: Theory and practice
An analysis of heuristics for graph planarization
Reconstruction graphs and testing their properties in a relational spatial database
Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
Clustered planarity testing revisited
Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
2-restricted extensions of partial embeddings of graphs
A dichotomy result for cyclic-order traversing games
Planar rectilinear drawings of outerplanar graphs in linear time
Property testing of planarity in the \textsf{CONGEST} model
An efficient parallel algorithm for computing a large independent set in a planar graph
Testing planarity of geometric automorphisms in linear time
On planar valued CSPs
The two basic linear time Planarity algorithms: Are they the same?
A matrix analysis of carrier posets of biconnected graphs
Canonical forms for cycles in bridge graphs
Beyond-planarity: Turán-type results for non-planar bipartite graphs
Planar median graphs and cubesquare-graphs
An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs
Approximating the rectilinear crossing number
The hybrid spanning tree problem
Embedding graphs into embedded graphs
Crossing-constrained hierarchical drawings

This page was built for publication: Efficient Planarity Testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4065028)