Efficient Planarity Testing

Cited in

(only showing first 100 items - show all)

Constructing compact rectilinear planar layouts using canonical representation of planar graphs
Approximating the minimum hub cover problem on planar graphs
Liar's domination in unit disk graphs
Drawing plane graphs nicely
Projective plan and Möbius band obstructions
Amortized Computational Complexity
Graph graphics: Theory and practice
Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
A characterization of planar graphs by Trémaux orders
Trémaux trees and planarity
A branch-and-cut approach to the crossing number problem
A very personal reminiscence on the problem of computational complexity
Menus of kuratowski subgraphs
A direct linear-time planarity test for unflippable modules
Depth First Search in the Semi-streaming Model
Cyclic Level Planarity Testing and Embedding
Facilities layout generalized model solved by n-boundary shortest path heuristics
Parameterized complexity of the spanning tree congestion problem
Algorithms for Drawing Planar p-petal Graphs
A matrix analysis of carrier posets of biconnected graphs
Canonical forms for cycles in bridge graphs
1-planarity of complete multipartite graphs
SPLITTING NUMBER is NP-complete
Edge-contraction problems
Recognition of DFS trees: Sequential and parallel algorithms with refined verifications
A Pfaffian formula for matching polynomials of outerplanar graphs
Trémaux trees and planarity
Caterpillar arboricity of planar graphs
Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs
Computing k-modal embeddings of planar digraphs
Elimination of local bridges
A linear-time certifying algorithm for recognizing generalized series-parallel graphs
Simple planar graph partition into three forests
Kuratowski's theorem
An efficient parallel algorithm for planarity
$A\,V^ 2$ algorithm for determining isomorphism of planar graphs
An algorithm for the characterization of the nonplanarity of a maximal graphical partition
A genetic algorithm for determining the thickness of a graph
Finding small simple cycle separators for 2-connected planar graphs
Planarity for clustered graphs
Parameterized graph cleaning problems
Planarity algorithms via PQ-trees (extended abstract)
Planarization of graphs embedded on surfaces
Counting cliques in 1-planar graphs
Finding strong components using depth-first search
Upward drawings of triconnected digraphs.
The optimal packing of eight points in the real projective plane
Treetopes and their graphs
A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
On the upward embedding on the torus
Hypergraph planarity and the complexity of drawing venn diagrams
Computing an st-numbering
Nonabelian flows in networks
New approximation algorithms for minimum cycle bases of graphs
Reconstruction graphs and testing their properties in a relational spatial database
Hardness of embedding simplicial complexes in R^d
Searching forK_3,3in linear time
Approximation algorithms for polynomial-expansion and low-density graphs
An O(n+m) certifying triconnnectivity algorithm for Hamiltonian graphs
Computational study on a PTAS for planar dominating set problem
Satisfiability of co-nested formulas
Enumerating homomorphisms
Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
Fast incremental planarity testing
A new approach to the linearity of testing planarity of graphs
Linkless and flat embeddings in 3-space
Dynamic DFS in undirected graphs: breaking the $O(m)$ barrier
Force-directed layout of order diagrams using dimensional reduction
A simple algorithm for 4-coloring 3-colorable planar graphs
Rikudo is NP-complete
Light sources, obstructions and spherical orders
$(t, s)$-completely independent spanning trees
An algorithm for reliability analysis of planar graphs
An algorithm for finding a large independent set in planar graphs
Upward planar morphs
Counting Unlabelled Subtrees of a Tree is #P-complete
The 2-linkage problem for acyclic digraphs
An annotated review on graph drawing and its applications
A V log V algorithm for isomorphism of triconnected planar graphs
TRÉMAUX TREES AND PLANARITY
Embeddings of graphs with no short noncontractible cycles
A 3-approximation for the pathwidth of Halin graphs
Establishing order in planar subdivisions
Approximating the rectilinear crossing number
A linear time algorithm for finding maximal planar subgraphs
Upward planar morphs
Triangulating planar graphs while minimizing the maximum degree
HV-planarity: algorithms and complexity
A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks
scientific article; zbMATH DE number 90553 (Why is no real title available?)
A linear algorithm for embedding planar graphs using PQ-trees
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
A direct proof of the strong Hanani-Tutte theorem on the projective plane
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
Clustered Planarity: Clusters with Few Outgoing Edges
Analogies between the crossing number and the tangle crossing number
Researches of semigroups with planar Cayley graphs: results and problems
A linear-time algorithm for finding an ambitus

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)