On the Computational Complexity of Upward and Rectilinear Planarity Testing
From MaRDI portal
Publication:2784472
DOI10.1137/S0097539794277123zbMath0996.68130OpenAlexW2018091581MaRDI QIDQ2784472
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794277123
algorithmcomputational complexityapproximation algorithmordered setplanar graphgraph drawingNP-complete problemlayoutorthogonal drawingplanar drawingrectilinear drawingupward drawing
Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Rectilinear Planarity of Partial 2-Trees ⋮ A topology-shape-metrics framework for ortho-radial graph drawing ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Sliding column model for t-unit bar visibility representations of graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Orthogonal layout with optimal face complexity ⋮ On orthogonally convex drawings of plane graphs ⋮ Planar rectilinear drawings of outerplanar graphs in linear time ⋮ Upward Planar Drawings with Three and More Slopes ⋮ Rooted Uniform Monotone Minimum Spanning Trees ⋮ Drawing two posets ⋮ HV-planarity: algorithms and complexity ⋮ Planar posets, dimension, breadth and the number of minimal elements ⋮ Monotone Drawings of 3-Connected Plane Graphs ⋮ Computing maximum upward planar subgraphs of single-source embedded digraphs ⋮ Algorithms and Bounds for L-Drawings of Directed Graphs ⋮ SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS ⋮ Advances on Testing C-Planarity of Embedded Flat Clustered Graphs ⋮ Drawings of planar graphs with few slopes and segments ⋮ Upward planar drawings with three and more slopes ⋮ Quasi-upward planar drawings with minimum curve complexity ⋮ Upward planarity testing ⋮ Orthogeodesic point-set embedding of trees ⋮ Nearly optimal monotone drawing of trees ⋮ Compact Monotone Drawing of Trees ⋮ Tree-width and dimension ⋮ Computing orthogonal drawings with the minimum number of bends ⋮ Extending Partial Orthogonal Drawings ⋮ Upward planar drawings with two slopes ⋮ Planar Embeddings with Small and Uniform Faces ⋮ Upward planar drawings on the standing and the rolling cylinders ⋮ Orthogonal Graph Drawing with Inflexible Edges ⋮ A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system ⋮ Universal slope sets for 1-bend planar drawings ⋮ Classification of Planar Upward Embedding ⋮ Upward Planarity Testing of Embedded Mixed Graphs ⋮ Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Planar Confluent Orthogonal Drawings of 4-Modal Digraphs ⋮ Unit-length rectangular drawings of graphs ⋮ Rectilinear planarity of partial 2-trees ⋮ Testing upward planarity of partial 2-trees ⋮ 1-Bend Upward Planar Drawings of SP-Digraphs ⋮ Bitonic st-orderings for Upward Planar Graphs ⋮ Orthogonal drawings and crossing numbers of the Kronecker product of two cycles ⋮ ON MINIMUM AREA PLANAR UPWARD DRAWINGS OF DIRECTED TREES AND OTHER FAMILIES OF DIRECTED ACYCLIC GRAPHS ⋮ On the Complexity of the Planar Slope Number Problem ⋮ 1-bend upward planar slope number of SP-digraphs ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Upward and quasi-upward planarity testing of embedded mixed graphs ⋮ Bend-optimal orthogonal drawings of triconnected plane graphs ⋮ On the area requirements of planar straight-line orthogonal drawings of ternary trees ⋮ Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity ⋮ Planar L-Drawings of Directed Graphs ⋮ Level planarity: transitivity vs. even crossings ⋮ On contact graphs of paths on a grid ⋮ Bend-minimum orthogonal drawings in quadratic time ⋮ Orthogonal graph drawing with flexibility constraints ⋮ Extending upward planar graph drawings ⋮ On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings ⋮ Maximum upward planar subgraphs of embedded planar digraphs ⋮ Orthogonal graph drawing with inflexible edges ⋮ Complexity results for three-dimensional orthogonal graph drawing ⋮ On the number of upward planar orientations of maximal planar graphs ⋮ Strip planarity testing for embedded planar graphs ⋮ Simultaneous Embeddings with Few Bends and Crossings ⋮ Unnamed Item ⋮ On embedding a graph in the grid with the maximum number of bends and other bad features ⋮ Upward three-dimensional grid drawings of graphs ⋮ Universal slope sets for upward planar drawings ⋮ Upward planar morphs ⋮ Improving the running time of embedded upward planarity testing ⋮ An Improved Upward Planarity Testing Algorithm and Related Applications ⋮ The partial visibility representation extension problem ⋮ Upward planar morphs ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Universal slope sets for upward planar drawings ⋮ Dimension and height for posets with planar cover graphs. ⋮ A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs ⋮ Connected Rectilinear Graphs on Point Sets ⋮ Upward planar graphs and their duals ⋮ Confluent Hasse Diagrams ⋮ Computing k-modal embeddings of planar digraphs ⋮ Volume requirements of 3D upward drawings ⋮ Accelerated Bend Minimization ⋮ Bounded Embeddings of Graphs in the Plane ⋮ Grid straight-line embeddings of trees with a minimum number of bends per path ⋮ Upward Book Embeddings of st-Graphs ⋮ Approximation Algorithms for Facial Cycles in Planar Embeddings ⋮ On the two-dimensional orthogonal drawing of series-parallel graphs ⋮ Upward Planarity Testing in Practice ⋮ Orthogonal planarity testing of bounded treewidth graphs ⋮ Three-dimensional orthogonal graph drawing algorithms ⋮ Graph layout for applications in compiler construction ⋮ TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY ⋮ Multilevel Planarity ⋮ Radial Level Planarity with Fixed Embedding ⋮ Right Angle Crossing Drawings of Graphs ⋮ Level-planarity: transitivity vs. even crossings ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters ⋮ Extending Partial Orthogonal Drawings ⋮ Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time ⋮ Towards area requirements for drawing hierarchically planar graphs
