Efficient Planarity Testing

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

Projective plan and Möbius band obstructions
SPLITTING NUMBER is NP-complete
Graph graphics: Theory and practice
A matrix analysis of carrier posets of biconnected graphs
Canonical forms for cycles in bridge graphs
Algorithms for Drawing Planar p-petal Graphs
A very personal reminiscence on the problem of computational complexity
Facilities layout generalized model solved by n-boundary shortest path heuristics
Parameterized complexity of the spanning tree congestion problem
Computing k-modal embeddings of planar digraphs
A linear-time certifying algorithm for recognizing generalized series-parallel graphs
Simple planar graph partition into three forests
$A\,V^ 2$ algorithm for determining isomorphism of planar graphs
A genetic algorithm for determining the thickness of a graph
An algorithm for the characterization of the nonplanarity of a maximal graphical partition
Finding strong components using depth-first search
Planarity algorithms via PQ-trees (extended abstract)
The optimal packing of eight points in the real projective plane
A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
Nonabelian flows in networks
Counting cliques in 1-planar graphs
Parameterized graph cleaning problems
Approximation algorithms for polynomial-expansion and low-density graphs
Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
$(t, s)$-completely independent spanning trees
Reconstruction graphs and testing their properties in a relational spatial database
Dynamic DFS in undirected graphs: breaking the $O(m)$ barrier
An $O(n+m)$ certifying triconnnectivity algorithm for Hamiltonian graphs
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
Searching forK_3,3in linear time
Force-directed layout of order diagrams using dimensional reduction
Rikudo is NP-complete
A simple algorithm for 4-coloring 3-colorable planar graphs
Upward planar morphs
Approximating the rectilinear crossing number
Title not available (Why is that?)
Establishing order in planar subdivisions
HV-planarity: algorithms and complexity
A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks
A direct proof of the strong Hanani-Tutte theorem on the projective plane
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?
On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs
Capacitated domination: problem complexity and approximation algorithms
On Boolean characterizations of planarity and planar embeddings of graphs
Limits of greedy approximation algorithms for the maximum planar subgraph problem
A simulated annealing algorithm for determining the thickness of a graph
An analysis of heuristics for graph planarization
Approximating the rectilinear crossing number
The complexity of finding minimal Voronoi covers with applications to machine learning
Checking the convexity of polytopes and the planarity of subdivisions (extended abstract)
The thickness of a minor-excluded class of graphs
A Note on the Minimum H-Subgraph Edge Deletion
On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves
Some problems in topological graph theory
Random walks and forbidden minors. I: An $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs
Non-planar core reduction of graphs
A simulated annealing algorithm for the maximum planar subgraph problem
Compact distributed certification of planar graphs
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
Algorithmic graph embeddings
Sewing ribbons on graphs in space
2-restricted extensions of partial embeddings of graphs
Property testing of planarity in the \textsf{CONGEST} model
Testing planarity of geometric automorphisms in linear time
Improved planarity algorithms
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
$(k,p)$-planarity: a relaxation of hybrid planarity
A simple recognition of maximal planar graphs
The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
Clustered planarity testing revisited
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
A method of graph reduction and its applications
Title not available (Why is that?)
Arkhipov's theorem, graph minors, and linear system nonlocal games
On planar valued CSPs
Optimizing concurrency under Scheduling by Edge Reversal
Coloring algorithms for $K_ 5$-minor free graphs
Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
Construction of floorplans for plane graphs over polygonal boundaries
On the Colin de Verdière graph number and penny graphs
The existence of homeomorphic subgraphs in chordal graphs
Upward planarity testing in practice: SAT formulations and comparative study
Planarity testing in parallel
Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
A tight lower bound for vertex planarization on graphs of bounded treewidth
Enumeration of articulation pairs of a planar graph
Planar median graphs and cubesquare-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)