Efficient Planarity Testing

Cited in

(only showing first 100 items - show all)

A V log V algorithm for isomorphism of triconnected planar graphs
A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
On two dual classes of planar graphs
Fixed edge-length graph drawing is NP-hard
A polyhedral approach to planar augmentation and related problems
Fast recognition of classes of almost-median graphs
On the thickness of graphs of given degree
Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
On the computational complexity of the bipartizing matching problem
Extending planar graph algorithms to \(K_{3,3}\)-free graphs
Boolean approach to planar embeddings of a graph
scientific article; zbMATH DE number 60387 (Why is no real title available?)
Triangulating planar graphs while minimizing the maximum degree
Counting Unlabelled Subtrees of a Tree is #P-complete
Atomic Embeddability, Clustered Planarity, and Thickenability
Invariants of graph drawings in the plane
Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
A computational approach to Conway's thrackle conjecture
An interactive layout heuristic based on hexagonal adjacency graphs
Drawing plane graphs nicely
Representation of graphs
The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
Fast incremental planarity testing
The complexity of planarity testing
Caterpillar arboricity of planar graphs
On characteristic and permanent polynomials of a matrix
Simultaneous scheduling and location (ScheLoc): The planar ScheLoc makespan problem
Every minor-closed property of sparse graphs is testable
Editing to a planar graph of given degrees
Upward planarity testing
Guthrie's problem: new equivalences and rapid reductions
On the complexity of chess
An efficient parallel algorithm for planarity
Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
An approach to the subgraph homeomorphism problem
Checking the convexity of polytopes and the planarity of subdivisions
Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
Determining the thickness of graphs is NP-hard
scientific article; zbMATH DE number 3762110 (Why is no real title available?)
A linear algorithm for the maximal planar subgraph problem
A satisfiability-based approach for embedding generalized tanglegrams on level graphs
Obtaining a Planar Graph by Vertex Deletion
Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs
Planarity for clustered graphs
A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
A characterization of planar graphs by Trémaux orders
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
A linear-time algorithm for finding an ambitus
An algorithm for imbedding cubic graphs in the torus
A search strategy for the elementary cycles of a directed graph
On graphical partitions and planarity
TRÉMAUX TREES AND PLANARITY
Embedding graphs in the torus in linear time
Trémaux trees and planarity
Trémaux trees and planarity
A branch-and-cut approach to the crossing number problem
Planarization of graphs embedded on surfaces
Amortized Computational Complexity
Boolean planarity characterization of graphs
Hardness of embedding simplicial complexes in \(\mathbb R^d\)
Treetopes and their graphs
Clustered Planarity: Clusters with Few Outgoing Edges
The minimum spanning tree problem on a planar graph
Network flows and non-guillotine cutting patterns
Strip planarity testing for embedded planar graphs
Characterization of curve map graphs
The recognition problem of graph search trees
MSOL restricted contractibility to planar graphs
Complexity results for the spanning tree congestion problem
Classes of cycle bases
An algorithm for finding a large independent set in planar graphs
On the recognition of search trees generated by BFS and DFS
A refinement of Kuratowski's theorem
Analysis of heuristics for finding a maximum weight planar subgraph
Connectivity of plane triangulations
Bipartite graphs, upward drawings, and planarity
How to draw a planar graph on a grid
Graph searches and their end vertices
Planar orientations with low out-degree and compaction of adjacency matrices
Certifying algorithms
On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
A new approach to the linearity of testing planarity of graphs
On the upward embedding on the torus
Enumerating homomorphisms
Graph isomorphism problem
A note on the complexity of matching patterns with variables
Graph-based generation of referring expressions
A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
Planar minimally rigid graphs and pseudo-triangulations
Approximation algorithms for Euler genus and related problems
Cyclic Level Planarity Testing and Embedding
Computing crossing numbers in quadratic time
Heuristics for the maximum outerplanar subgraph problem
Greedy drawings of triangulations
Linkless and flat embeddings in 3-space
Determining when a graphic matroid is transversal in linear time
Computing an st-numbering
Untangling a planar graph

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)