Efficient Planarity Testing

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

Projective plan and Möbius band obstructions
SPLITTING NUMBER is NP-complete
A matrix analysis of carrier posets of biconnected graphs
Canonical forms for cycles in bridge graphs
Facilities layout generalized model solved by n-boundary shortest path heuristics
Simple planar graph partition into three forests
A genetic algorithm for determining the thickness of a graph
Finding strong components using depth-first search
A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
Approximation algorithms for polynomial-expansion and low-density graphs
$(t, s)$-completely independent spanning trees
Reconstruction graphs and testing their properties in a relational spatial database
Computational study on a PTAS for planar dominating set problem
An algorithm for reliability analysis of planar graphs
An annotated review on graph drawing and its applications
Approximating the rectilinear crossing number
Title not available (Why is that?)
Analogies between the crossing number and the tangle crossing number
Simpler algorithms for testing two-page book embedding of partitioned graphs
The two basic linear time Planarity algorithms: Are they the same?
Capacitated domination: problem complexity and approximation algorithms
On Boolean characterizations of planarity and planar embeddings of graphs
Approximating the rectilinear crossing number
The thickness of a minor-excluded class of graphs
On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves
Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
Every triangle-free planar graph has a planar upward drawing
Line directionality of orders
The hybrid spanning tree problem
Sewing ribbons on graphs in space
2-restricted extensions of partial embeddings of graphs
Data Structures and their Planar Graph Layouts
Linear-time recognition of map graphs with outerplanar witness
On counting planar embeddings
Certifying induced subgraphs in large graphs
Gap strings and spanning forests for bridge graphs of biconnected graphs
The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
O(n2) algorithms for graph planarization
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
Finding the closed partition of a planar graph
Title not available (Why is that?)
Arkhipov's theorem, graph minors, and linear system nonlocal games
Construction of floorplans for plane graphs over polygonal boundaries
On the Colin de Verdière graph number and penny graphs
Planarity testing in parallel
Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
Embedding graphs into embedded graphs
Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
An algebra for pomsets.
Graph Search Trees and Their Leaves
A dichotomy result for cyclic-order traversing games
Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks
A large set of torus obstructions and how they were discovered
Title not available (Why is that?)
Grid recognition: classical and parameterized computational perspectives
Kernelization for finding lineal topologies (depth-first spanning trees) with many or few leaves
Crossing-constrained hierarchical drawings
Determining outerplanarity using segment graphs
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
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

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)