Efficient Planarity Testing
From MaRDI portal
Publication:4065028
DOI10.1145/321850.321852zbMath0307.68025OpenAlexW1987374783WikidataQ54153205 ScholiaQ54153205MaRDI QIDQ4065028
John E. Hopcrofts, Robert Endre Tarjan
Publication date: 1974
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6011
Planar graphs; geometric and topological aspects of graph theory (05C10) Algorithms in computer science (68W99)
Related Items
Planar rectilinear drawings of outerplanar graphs in linear time, On the orbits of the product of two permutations, The hybrid spanning tree problem, Recognizing graph search trees, Analogies between the crossing number and the tangle crossing number, Caterpillar arboricity of planar graphs, HV-planarity: algorithms and complexity, The complexity of planarity testing, Computing crossing numbers in quadratic time, Planarity testing in parallel, The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, Upward planarity testing, On planar valued CSPs, Graph searches and their end vertices, Linear-time recognition of map graphs with outerplanar witness, The existence of homeomorphic subgraphs in chordal graphs, Tree-width and dimension, Property testing of planarity in the \textsf{CONGEST} model, A tight lower bound for vertex planarization on graphs of bounded treewidth, A method of graph reduction and its applications, Finding a path with two labels forbidden in group-labeled graphs, Drawing planar graphs using the canonical ordering, Maximum planar subgraphs and nice embeddings: Practical layout tools, On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm, The thickness of a minor-excluded class of graphs, Computing the flip distance between triangulations, \((k,p)\)-planarity: a relaxation of hybrid planarity, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Gap strings and spanning forests for bridge graphs of biconnected graphs, New results on drawing angle graphs, Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time, Projective plan and Möbius band obstructions, On characteristic and permanent polynomials of a matrix, Algorithmic graph embeddings, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Simple planar graph partition into three forests, On the computational complexity of the bipartizing matching problem, Dynamic planar embeddings of dynamic graphs, On universal positive graphs, Treetopes and their graphs, An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs, Obtaining a planar graph by vertex deletion, Optimal polygonal representation of planar graphs, A large set of torus obstructions and how they were discovered, Planar median graphs and cubesquare-graphs, Towards optimal kernel for connected vertex cover in planar graphs, Embedding graphs into embedded graphs, The QuaSEFE problem, Liar's domination in unit disk graphs, Graphs with no \(K_{3,3}\) minor containing a fixed edge, The isomorphism problem for planar 3-connected graphs is in unambiguous logspace, A new planarity test, A note on the complexity of matching patterns with variables, Graphs whose complement and square are isomorphic, Orthogonal drawings of graphs for the automation of VLSI circuit design, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, A linear-time algorithm for testing full outer-2-planarity, Crossing-constrained hierarchical drawings, Computational study on a PTAS for planar dominating set problem, Simpler algorithms for testing two-page book embedding of partitioned graphs, Parameterized complexity of the spanning tree congestion problem, Planar graph bipartization in linear time, An experimental comparison of four graph drawing algorithms., 2-restricted extensions of partial embeddings of graphs, A V log V algorithm for isomorphism of triconnected planar graphs, Simultaneous scheduling and location (ScheLoc): The planar ScheLoc makespan problem, Planar minimally rigid graphs and pseudo-triangulations, On Boolean characterizations of planarity and planar embeddings of graphs, Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks, Dimension and height for posets with planar cover graphs., Compact distributed certification of planar graphs, Short encodings of planar graphs and maps, The minimum spanning tree problem on a planar graph, Fixed edge-length graph drawing is NP-hard, \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs, Facilities layout generalized model solved by n-boundary shortest path heuristics, Advances in the theory and practice of graph drawing, An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs, Planar drawings of fixed-mobile bigraphs, A simulated annealing algorithm for determining the thickness of a graph, Approximating the rectilinear crossing number, On the recognition of search trees generated by BFS and DFS, Heuristics for the maximum outerplanar subgraph problem, Sewing ribbons on graphs in space, An algebra for pomsets., Every triangle-free planar graph has a planar upward drawing, Line directionality of orders, Capacitated domination: problem complexity and approximation algorithms, A linear-time certifying algorithm for recognizing generalized series-parallel graphs, On counting planar embeddings, The complexity of finding minimal Voronoi covers with applications to machine learning, A genetic algorithm for determining the thickness of a graph, Counting cliques in 1-planar graphs, Reconstruction graphs and testing their properties in a relational spatial database, Finding the closed partition of a planar graph, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs, Satisfiability of co-nested formulas, Force-directed layout of order diagrams using dimensional reduction, Rikudo is NP-complete, Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs, A linear algorithm for embedding planar graphs using PQ-trees, A unified approach to visibility representations of planar graphs, Rectilinear planar layouts and bipolar orientations of planar graphs, Finding small simple cycle separators for 2-connected planar graphs, A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs, A note on approximating graph genus, Path-based depth-first search for strong and biconnected components, A very personal reminiscence on the problem of computational complexity, Planar posets, dimension, breadth and the number of minimal elements, Approximate tree decompositions of planar graphs in linear time, An algorithm for the characterization of the nonplanarity of a maximal graphical partition, Complexity of metric dimension on planar graphs, Greedy drawings of triangulations, Graph graphics: Theory and practice, On finding optimal and near-optimal lineal spanning trees, A topological approach to dynamic graph connectivity, Fast recognition of classes of almost-median graphs, An efficient parallel algorithm for planarity, Establishing order in planar subdivisions, Classes of cycle bases, A new approach to the linearity of testing planarity of graphs, Embedding planar graphs in four pages, Hex ist Pspace-vollständig. (Hex is Pspace-complete), An algorithm for imbedding cubic graphs in the torus, Hardness of embedding simplicial complexes in \(\mathbb R^d\), Clustered planarity testing revisited, 1-planarity of complete multipartite graphs, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Enumerating homomorphisms, Linkless and flat embeddings in 3-space, Errors in graph embedding algorithms, On the complexity of the edge-disjoint min-min problem in planar digraphs, New approximation algorithms for minimum cycle bases of graphs, Coloring algorithms for \(K_ 5\)-minor free graphs, Connectivity of plane triangulations, Representation of graphs, Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs, Improved planarity algorithms, Embeddings of graphs with no short noncontractible cycles, On two dual classes of planar graphs, Bipartite graphs, upward drawings, and planarity, A graphical criterion of planarity for RNA secondary structures with pseudoknots in Rivas-Eddy class, Certifying algorithms, Treewidth lower bounds with brambles, On the thickness of graphs of given degree, Trémaux trees and planarity, Planar orientations with low out-degree and compaction of adjacency matrices, A linear-time algorithm for finding an ambitus, How to find Steiner minimal trees in Euclidean \(d\)-space, Guthrie's problem: new equivalences and rapid reductions, A linear-time algorithm for drawing a planar graph on a grid, Area requirement and symmetry display of planar upward drawings, Light sources, obstructions and spherical orders, Constructing compact rectilinear planar layouts using canonical representation of planar graphs, A branch-and-cut approach to the crossing number problem, Certifying 3-edge-connectivity, Planar lattices are lexicographically shellable, Recognition of DFS trees: Sequential and parallel algorithms with refined verifications, Strip planarity testing for embedded planar graphs, Upward drawings of triconnected digraphs., MSOL restricted contractibility to planar graphs, Every minor-closed property of sparse graphs is testable, An interactive layout heuristic based on hexagonal adjacency graphs, Parameterized graph cleaning problems, A computational approach to Conway's thrackle conjecture, A simple algorithm for 4-coloring 3-colorable planar graphs, 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, Computing an st-numbering, A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networks, Extending planar graph algorithms to \(K_{3,3}\)-free graphs, On graphical partitions and planarity, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Editing to a planar graph of given degrees, On the upward embedding on the torus, Non-planar core reduction of graphs, Testing planarity of geometric automorphisms in linear time, Checking the convexity of polytopes and the planarity of subdivisions, A simple recognition of maximal planar graphs, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Structure and recognition of graphs with no 6-wheel subdivision, Invariants of graph drawings in the plane, Untangling a planar graph, A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, On the complexity of chess, Edge-contraction problems, Network flows and non-guillotine cutting patterns, The 2-linkage problem for acyclic digraphs, Graph isomorphism problem, Drawing plane graphs nicely, Characterization of curve map graphs, A refinement of Kuratowski's theorem, Depth-first search is inherently sequential, An approach to the subgraph homeomorphism problem, Analysis of heuristics for finding a maximum weight planar subgraph, How to draw a planar graph on a grid, A characterization of planar graphs by Trémaux orders, An efficient parallel algorithm for computing a large independent set in a planar graph, Enumeration of articulation pairs of a planar graph, Determining the thickness of graphs is NP-hard, Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, Unnamed Item, Searching forK3,3in linear time, Solides non organisés : définition, implantation et plongement, Boolean approach to planar embeddings of a graph, A linear algorithm for the maximal planar subgraph problem, Planarity Algorithms via PQ-Trees (Extended Abstract), Trémaux Trees and Planarity, Parameterized Graph Cleaning Problems, Ranking and unranking planar embeddings, Atomic Embeddability, Clustered Planarity, and Thickenability, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Amortized Computational Complexity, ON FINDING SPARSE THREE-EDGE-CONNECTED AND THREE-VERTEX-CONNECTED SPANNING SUBGRAPHS, A simulated annealing algorithm for the maximum planar subgraph problem, Desert island theorems, Bijective comparison of optimal planarity algorithms, Approximation Algorithms for Euler Genus and Related Problems, Determining when a graphic matroid is transversal in linear time, Branch-and-bound techniques for the maximum planar subgraph problem∗, The Optimal Packing of Eight Points in the Real Projective Plane, Checking the convexity of polytopes and the planarity of subdivisions (extended abstract), A Note on the Minimum H-Subgraph Edge Deletion, Obstructions for the Disk and the Cylinder Embedding Extension Problems, Linearizing partial search orders, Graph-Based Generation of Referring Expressions, Embedding graphs in the torus in linear time, A matrix analysis of carrier posets of biconnected graphs, Canonical forms for cycles in bridge graphs, Obtaining a Planar Graph by Vertex Deletion, Unnamed Item, Approximating the Rectilinear Crossing Number, A Direct Proof of the Strong Hanani–Tutte Theorem on the Projective Plane, Listing all spanning trees in Halin graphs — sequential and Parallel view, Using Brouwer’s Fixed Point Theorem, Unnamed Item, An algorithm for reliability analysis of planar graphs, The number of Reidemeister moves needed for unknotting, Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs, Hypergraph planarity and the complexity of drawing venn diagrams, An analysis of heuristics for graph planarization, Menus of kuratowski subgraphs, Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs, A direct linear-time planarity test for unflippable modules, Algorithms, Blocks of Hypergraphs, Data Structures and their Planar Graph Layouts, A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs, A search strategy for the elementary cycles of a directed graph, Unnamed Item, How to Cut a Graph into Many Pieces, Planarity Testing Revisited, A 3-approximation for the pathwidth of Halin graphs, Boolean planarity characterization of graphs, Crossing Number is NP-Complete, A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs, SPLITTING NUMBER is NP-complete, Unnamed Item, Vertex-edge domination in unit disk graphs, Matching and spanning in certain planar graphs, The two basic linear time Planarity algorithms: Are they the same?, Hanani-Tutte for approximating maps of graphs, On dispersable book embeddings, Unnamed Item, Unnamed Item, Complexity Results for the Spanning Tree Congestion Problem, Triangulating planar graphs while minimizing the maximum degree, Upward planar morphs, Upward planar morphs, Clustered Planarity: Clusters with Few Outgoing Edges, Cyclic Level Planarity Testing and Embedding, Efficient Extraction of Multiple Kuratowski Subdivisions, Approximating the minimum hub cover problem on planar graphs, Fast incremental planarity testing, Some problems in topological graph theory, Unnamed Item, Computing k-modal embeddings of planar digraphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem, Unnamed Item, Depth First Search in the Semi-streaming Model, A dichotomy result for cyclic-order traversing games, Upward Planarity Testing in Practice, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Algorithms for Drawing Planar p-petal Graphs, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, TRÉMAUX TREES AND PLANARITY, Radial Level Planarity with Fixed Embedding, Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs, Determining outerplanarity using segment graphs, The Recognition Problem of Graph Search Trees, A Pfaffian formula for matching polynomials of outerplanar graphs, Quantitative Restrictions on Crossing Patterns, $$\textit{\textbf{k}}$$-Planar Graphs, An algorithm for finding a large independent set in planar graphs, Kuratowski's theorem, Unnamed Item, Counting Unlabelled Subtrees of a Tree is #P-complete, Nonabelian flows in networks, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Optimizing concurrency under Scheduling by Edge Reversal, Arkhipov's theorem, graph minors, and linear system nonlocal games, Planarity for clustered graphs, A polyhedral approach to planar augmentation and related problems, A fast approximation algorithm for the maximum 2-packing set problem on planar graphs, Planarization of graphs embedded on surfaces, An annotated review on graph drawing and its applications, Grid recognition: classical and parameterized computational perspectives, On the construction of planar embedding for a class of orthogonal polyhedra, DFS tree construction: Algorithms and characterizations, O(n2) algorithms for graph planarization, Algorithmic graph embeddings, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
