Partial and constrained level planarity

DOI10.1016/J.TCS.2025.115291MaRDI QIDQ6975891zbMATH OpenFDO

Authors Guido Brückner, Ignaz Rutter

Publication date 2 June 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115291

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A Kuratowski-type theorem for planarity of partially embedded graphs
• A new planarity test
• A satisfiability formulation of problems on level graphs
• A Theorem on Boolean Matrices
• Advancements on SEFE and partitioned book embedding problems
• An SPQR-tree-like embedding representation for upward planarity
• Atomic embeddability, clustered planarity, and thickenability
• Beyond level planarity: cyclic, torus, and simultaneous level planarity
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Contact representations of planar graphs: extending a partial representation is hard
• Disconnectivity and relative positions in simultaneous embeddings
• Drawing simultaneously embedded graphs with few bends
• Experimental comparison of PC-trees and PQ-trees
• Extending convex partial drawings of graphs
• Extending partial representations of circle graphs
• Extending partial representations of function graphs and permutation graphs
• Extending partial representations of interval graphs
• Extending partial representations of proper and unit interval graphs
• Extending partial representations of subclasses of chordal graphs
• Extending partial representations of trapezoid graphs
• Extending upward planar graph drawings
• Fast Algorithms for Finding Nearest Common Ancestors
• Hanani-Tutte for Radial Planarity
• Hierarchies and planarity theory
• scientific article; zbMATH DE number 1377359 (Why is no real title available?)
• scientific article; zbMATH DE number 7691271 (Why is no real title available?)
• Intersection-link representations of graphs
• Level Planar Embedding in Linear Time
• Level planarity is more difficult than we thought (poster abstract)
• Level planarity: transitivity vs. even crossings
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Optimal binary space partitions for segments in the plane
• Ordered level planarity and its relationship to geodesic planarity, bi-monotonicity, and variations of level planarity
• Parameterized algorithms for upward planarity
• PC trees and circular-ones arrangements.
• Practical Level Planarity Testing and Layout with Embedding Constraints
• Radial Level Planarity Testing and Embedding in Linear Time
• Simultaneous Embedding
• Simultaneous embedding: edge orderings, relative positions, cutvertices
• Simultaneous Geometric Graph Embeddings
• Simultaneous interval graphs
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Synchronized planarity with applications to constrained planarity problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Testing Planarity of Partially Embedded Graphs
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• The importance of being proper
• The simultaneous representation problem for chordal, comparability and permutation graphs
• Toward a theory of planarity: Hanani-Tutte and planarity variants
• Upward planar drawings on the standing and the rolling cylinders

This page was built for publication: Partial and constrained level planarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6975891)