Efficient Planarity Testing

Cited in

(only showing first 100 items - show all)

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
Finding small simple cycle separators for 2-connected planar graphs
Dimension and height for posets with planar cover graphs.
Light sources, obstructions and spherical orders
How to Cut a Graph into Many Pieces
An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
A linear algorithm for embedding planar graphs using PQ-trees
Edge-contraction problems
Algorithmic graph embeddings
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Area requirement and symmetry display of planar upward drawings
Short encodings of planar graphs and maps
1-planarity of complete multipartite graphs
An experimental comparison of four graph drawing algorithms.
Blocks of hypergraphs. Applied to hypergraphs and outerplanarity
Towards optimal kernel for connected vertex cover in planar graphs
On the complexity of the edge-disjoint min-min problem in planar digraphs
Elimination of local bridges
Recognizing graph search trees
Embedding planar graphs in four pages
Kuratowski's theorem
Structure and recognition of graphs with no 6-wheel subdivision
Advances in the theory and practice of graph drawing
Planar posets, dimension, breadth and the number of minimal elements
How to find Steiner minimal trees in Euclidean $d$-space
Approximate tree decompositions of planar graphs in linear time
Obtaining a planar graph by vertex deletion
New approximation algorithms for minimum cycle bases of graphs
Depth-first search is inherently sequential
Embeddings of graphs with no short noncontractible cycles
A new planarity test
Drawing planar graphs using the canonical ordering
Complexity of metric dimension on planar graphs
Hypergraph planarity and the complexity of drawing venn diagrams
Liar's domination in unit disk graphs
A 3-approximation for the pathwidth of Halin graphs
A linear time algorithm for finding maximal planar subgraphs
A unified approach to visibility representations of planar graphs
Rectilinear planar layouts and bipolar orientations of planar graphs
A Pfaffian formula for matching polynomials of outerplanar graphs
Tree-width and dimension
A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs
Upward drawings of triconnected digraphs.
Crossing Number is NP-Complete
Maximum planar subgraphs and nice embeddings: Practical layout tools
A linear-time algorithm for drawing a planar graph on a grid
A linear-time algorithm for testing full outer-2-planarity
Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs
The 2-linkage problem for acyclic digraphs
Path-based depth-first search for strong and biconnected components
A note on approximating graph genus
Linear algorithms to recognize outerplanar and maximal outerplanar graphs
Treewidth lower bounds with brambles
On the orbits of the product of two permutations
Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
A topological approach to dynamic graph connectivity
Planar graph bipartization in linear time
On finding optimal and near-optimal lineal spanning trees
New results on drawing angle graphs
The number of Reidemeister moves needed for unknotting
Hex ist Pspace-vollständig. (Hex is Pspace-complete)
Satisfiability of co-nested formulas
Errors in graph embedding algorithms
Hanani-Tutte for approximating maps of graphs
Obstructions for the Disk and the Cylinder Embedding Extension Problems
Using Brouwer’s Fixed Point Theorem
Upward planarity testing in practice: SAT formulations and comparative study
A very personal reminiscence on the problem of computational complexity
Branch-and-bound techniques for the maximum planar subgraph problem^∗
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
Graphs with no $K_{3,3}$ minor containing a fixed edge
Efficient Extraction of Multiple Kuratowski Subdivisions
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
Planarity testing revisited
Approximating the minimum hub cover problem on planar graphs
A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas-Eddy class
A simulated annealing algorithm for determining the thickness of a 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)