Efficient Planarity Testing

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

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
The 2-linkage problem for acyclic digraphs
Embeddings of graphs with no short noncontractible cycles
A linear algorithm for embedding planar graphs using PQ-trees
Planar orientations with low out-degree and compaction of adjacency matrices
A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
A linear-time algorithm for testing full outer-2-planarity
A note on approximating graph genus
Treewidth lower bounds with brambles
Planar minimally rigid graphs and pseudo-triangulations
Short encodings of planar graphs and maps
Path-based depth-first search for strong and biconnected components
New results on drawing angle graphs
Obstructions for the Disk and the Cylinder Embedding Extension Problems
How to draw a planar graph on a grid
Greedy drawings of triangulations
The number of Reidemeister moves needed for unknotting
Planar posets, dimension, breadth and the number of minimal elements
Approximate tree decompositions of planar graphs in linear time
A linear-time algorithm for drawing a planar graph on a grid
Maximum planar subgraphs and nice embeddings: Practical layout tools
Approximation algorithms for Euler genus and related problems
Depth-first search is inherently sequential
A new planarity test
Complexity of metric dimension on planar graphs
A unified approach to visibility representations of planar graphs
Rectilinear planar layouts and bipolar orientations of planar graphs
A topological approach to dynamic graph connectivity
On finding optimal and near-optimal lineal spanning trees
Untangling a planar graph
Area requirement and symmetry display of planar upward drawings
Recognizing graph search trees
Obtaining a planar graph by vertex deletion
Linear algorithms to recognize outerplanar and maximal outerplanar graphs
Embedding planar graphs in four pages
Bipartite graphs, upward drawings, and planarity
Algorithmic graph embeddings
On the complexity of the edge-disjoint min-min problem in planar digraphs
Advances in the theory and practice of graph drawing
On the orbits of the product of two permutations
Using Brouwer’s Fixed Point Theorem
Graph searches and their end vertices
Errors in graph embedding algorithms
Graph-based generation of referring expressions
Heuristics for the maximum outerplanar subgraph problem
An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
Hex ist Pspace-vollständig. (Hex is Pspace-complete)
On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
How to find Steiner minimal trees in Euclidean \(d\)-space
Structure and recognition of graphs with no 6-wheel subdivision
Drawing planar graphs using the canonical ordering
Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs
Certifying algorithms
How to Cut a Graph into Many Pieces
Blocks of hypergraphs. Applied to hypergraphs and outerplanarity
Computing crossing numbers in quadratic time
Towards optimal kernel for connected vertex cover in planar graphs
Planar graph bipartization in linear time
Tree-width and dimension
A note on the complexity of matching patterns with variables
An experimental comparison of four graph drawing algorithms.
Determining when a graphic matroid is transversal in linear time
Crossing Number is NP-Complete
Dimension and height for posets with planar cover graphs.
Hanani-Tutte for approximating maps of graphs
Graph isomorphism problem
Liar's domination in unit disk graphs
On the construction of planar embedding for a class of orthogonal polyhedra
Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks
Dynamic planar embeddings of dynamic graphs
Planarity testing revisited
A large set of torus obstructions and how they were discovered
Title not available (Why is that?)
An efficient parallel algorithm for computing a large independent set in a planar graph
Orthogonal drawings of graphs for the automation of VLSI circuit design
Graphs whose complement and square are isomorphic
Efficient Extraction of Multiple Kuratowski Subdivisions
The QuaSEFE problem

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)