Efficient Planarity Testing

Cited in

(only showing first 100 items - show all)

Improved planarity algorithms
Sewing ribbons on graphs in space
Orthogonal drawings of graphs for the automation of VLSI circuit design
Algorithmic graph embeddings
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
An algorithm for the characterization of the nonplanarity of a maximal graphical partition
A genetic algorithm for determining the thickness of a graph
Graphs whose complement and square are isomorphic
Establishing order in planar subdivisions
scientific article; zbMATH DE number 90553 (Why is no real title available?)
Upward planar morphs
A linear-time certifying algorithm for recognizing generalized series-parallel graphs
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
Capacitated domination: problem complexity and approximation algorithms
Linearizing partial search orders
Non-planar core reduction of graphs
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
Constructing compact rectilinear planar layouts using canonical representation of planar graphs
On finding sparse three-edge-connected and three-vertex-connected spanning subgraphs
Vertex-edge domination in unit disk graphs
Algorithms for Drawing Planar p-petal Graphs
Computational study on a PTAS for planar dominating set problem
On Boolean characterizations of planarity and planar embeddings of graphs
Planarity algorithms via PQ-trees (extended abstract)
Upward planar morphs
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^∗
Graphs with no $K_{3,3}$ minor containing a fixed edge
Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks
Efficient Extraction of Multiple Kuratowski Subdivisions
A large set of torus obstructions and how they were discovered
Planarity testing revisited
Simple planar graph partition into three forests
Approximating the minimum hub cover problem on planar graphs
Planarity testing in parallel
An algorithm for reliability analysis of planar graphs
A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas-Eddy class
Facilities layout generalized model solved by n-boundary shortest path heuristics
A simulated annealing algorithm for determining the thickness of a graph
Parameterized complexity of the spanning tree congestion problem
Data Structures and their Planar Graph Layouts
Searching forK_3,3in linear time
Gap strings and spanning forests for bridge graphs of biconnected graphs
Limits of greedy approximation algorithms for the maximum planar subgraph problem
A simulated annealing algorithm for the maximum planar subgraph problem
An algebra for pomsets.
HV-planarity: algorithms and complexity
Computing the flip distance between triangulations
The optimal packing of eight points in the real projective plane
Matching and spanning in certain planar graphs
Linear-time recognition of map graphs with outerplanar witness
Computing k-modal embeddings of planar digraphs
Optimizing concurrency under Scheduling by Edge Reversal
Determining outerplanarity using segment graphs
$A\,V^ 2$ algorithm for determining isomorphism of planar graphs
A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
scientific article; zbMATH DE number 7651152 (Why is no real title available?)
Dynamic planar embeddings of dynamic graphs
The complexity of finding minimal Voronoi covers with applications to machine learning
Force-directed layout of order diagrams using dimensional reduction
Solides non organisés : définition, implantation et plongement
Finding the closed partition of a planar graph
Algorithms
Rikudo is NP-complete
Approximation algorithms for polynomial-expansion and low-density graphs
$(k,p)$-planarity: a relaxation of hybrid planarity
Analogies between the crossing number and the tangle crossing number
Projective plan and Möbius band obstructions
Compact distributed certification of planar graphs
Some problems in topological graph theory
A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks
Checking the convexity of polytopes and the planarity of subdivisions (extended abstract)
A method of graph reduction and its applications
Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
On universal positive graphs
A direct proof of the strong Hanani-Tutte theorem on the projective plane
The thickness of a minor-excluded class of graphs
Coloring algorithms for $K_ 5$-minor free graphs
Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs
Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
Approximating the rectilinear crossing number
Planar lattices are lexicographically shellable
Depth First Search in the Semi-streaming Model
Indexing graph search trees and applications
A simple recognition of maximal planar graphs
The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
On the construction of planar embedding for a class of orthogonal polyhedra
A tight lower bound for vertex planarization on graphs of bounded treewidth
Simpler algorithms for testing two-page book embedding of partitioned graphs
scientific article; zbMATH DE number 7662167 (Why is no real title available?)
The QuaSEFE problem
A Note on the Minimum H-Subgraph Edge Deletion
The existence of homeomorphic subgraphs in chordal graphs
Enumeration of articulation pairs of a planar graph
On counting planar embeddings
Parameterized Graph Cleaning Problems
A simple algorithm for 4-coloring 3-colorable planar graphs
Every triangle-free planar graph has a planar upward drawing
Line directionality of orders

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)