Efficient Planarity Testing

Cited In (only showing first 100 items - show all)

Drawing plane graphs nicely
A characterization of planar graphs by Trémaux orders
Trémaux trees and planarity
Trémaux trees and planarity
A branch-and-cut approach to the crossing number problem
Caterpillar arboricity of planar graphs
Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
An efficient parallel algorithm for planarity
Planarity for clustered graphs
Planarization of graphs embedded on surfaces
Treetopes and their graphs
Fast incremental planarity testing
Hardness of embedding simplicial complexes in \(\mathbb R^d\)
An algorithm for finding a large independent set in planar graphs
Counting Unlabelled Subtrees of a Tree is #P-complete
TRÉMAUX TREES AND PLANARITY
A V log V algorithm for isomorphism of triconnected planar graphs
Triangulating planar graphs while minimizing the maximum degree
Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation
Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
Clustered Planarity: Clusters with Few Outgoing Edges
On the computational complexity of the bipartizing matching problem
Finding a path in group-labeled graphs with two labels forbidden
A linear-time algorithm for finding an ambitus
An interactive layout heuristic based on hexagonal adjacency graphs
The recognition problem of graph search trees
Complexity results for the spanning tree congestion problem
Extending planar graph algorithms to \(K_{3,3}\)-free graphs
On the recognition of search trees generated by BFS and DFS
A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
Analysis of heuristics for finding a maximum weight planar subgraph
On the complexity of chess
An approach to the subgraph homeomorphism problem
A linear algorithm for the maximal planar subgraph problem
A satisfiability-based approach for embedding generalized tanglegrams on level graphs
Title not available (Why is that?)
The complexity of planarity testing
A search strategy for the elementary cycles of a directed graph
Embedding graphs in the torus in linear time
Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs
Atomic Embeddability, Clustered Planarity, and Thickenability
The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
Upward planarity testing
Classes of cycle bases
Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
Obtaining a Planar Graph by Vertex Deletion
On graphical partitions and planarity
Determining the thickness of graphs is NP-hard
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
On the thickness of graphs of given degree
Invariants of graph drawings in the plane
On characteristic and permanent polynomials of a matrix
Title not available (Why is that?)
On two dual classes of planar graphs
A polyhedral approach to planar augmentation and related problems
Simultaneous scheduling and location (ScheLoc): The planar ScheLoc makespan problem
Checking the convexity of polytopes and the planarity of subdivisions
An algorithm for imbedding cubic graphs in the torus
A refinement of Kuratowski's theorem
Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
The minimum spanning tree problem on a planar graph
The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
A computational approach to Conway's thrackle conjecture
Network flows and non-guillotine cutting patterns
Characterization of curve map graphs
Connectivity of plane triangulations
Fixed edge-length graph drawing is NP-hard
Every minor-closed property of sparse graphs is testable
Certifying 3-edge-connectivity
Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
Fast recognition of classes of almost-median graphs
Representation of graphs
Editing to a planar graph of given degrees
Boolean planarity characterization of graphs
Guthrie's problem: new equivalences and rapid reductions
Amortized Computational Complexity
Strip planarity testing for embedded planar graphs
MSOL restricted contractibility to planar graphs
Cyclic Level Planarity Testing and Embedding
A Pfaffian formula for matching polynomials of outerplanar graphs
Edge-contraction problems
1-planarity of complete multipartite graphs
Elimination of local bridges
Kuratowski's theorem
Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs
Finding small simple cycle separators for 2-connected planar graphs
Hypergraph planarity and the complexity of drawing venn diagrams
Upward drawings of triconnected digraphs.
Optimal polygonal representation of planar graphs
On the upward embedding on the torus
Computing an st-numbering
New approximation algorithms for minimum cycle bases of graphs
Satisfiability of co-nested formulas
A new approach to the linearity of testing planarity of graphs
Enumerating homomorphisms
Linkless and flat embeddings in 3-space
Light sources, obstructions and spherical orders
A linear time algorithm for finding maximal planar subgraphs
A 3-approximation for the pathwidth of Halin graphs

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)