Simultaneous orthogonal planarity

DOI10.1007/978-3-319-50106-2_41MaRDI QIDQ2961544zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Giuseppe Di Battista, Peter Eades, Philipp Kindermann, Jan Kratochvíl, Fabian Lipp, Ignaz Rutter

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08427

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: We introduce and study the $extitOrthoSEFE-k$ problem: Given $k$ planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the $k$ graphs? We show that the problem is NP-complete for $kgeq3$ even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for $kgeq2$ even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for $k=2$ when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.

Recommendations

• Simultaneous embedding of embedded planar graphs
• Simultaneous embedding of embedded planar graphs
• On Some $\mathcal{NP}$ -complete SEFE Problems
• On the \(\mathcal{NP}\)-hardness of \textsc{GRacSim drawing} and \(k\)-SEFE problems
• Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges

Cites work

• scientific article; zbMATH DE number 3165199 (Why is no real title available?)
• scientific article; zbMATH DE number 4094812 (Why is no real title available?)
• scientific article; zbMATH DE number 1052322 (Why is no real title available?)
• scientific article; zbMATH DE number 1947397 (Why is no real title available?)
• A better heuristic for orthogonal graph drawings
• A new perspective on clustered planarity as a combinatorial embedding problem
• Advancements on SEFE and partitioned book embedding problems
• Beyond level planarity
• Disconnectivity and relative positions in simultaneous embeddings
• Geometric RAC simultaneous drawings of graphs
• Intersection Graphs in Simultaneous Embedding with Fixed Edges
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On-Line Planarity Testing
• On-line maintenance of triconnected components with SPQR-trees
• Simultaneous Geometric Graph Embeddings
• Simultaneous drawing of planar graphs with right-angle crossings and few bends
• Simultaneous interval graphs
• Simultaneous orthogonal planarity
• Testing simultaneous planarity when the common graph is 2-connected
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• The complexity of satisfiability problems
• The simultaneous representation problem for chordal, comparability and permutation graphs
• Toward a theory of planarity: Hanani-Tutte and planarity variants

Cited in

(9)

• Level-planar drawings with few slopes
• Simultaneous orthogonal planarity
• Extending partial orthogonal drawings
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• Unit-length rectangular drawings of graphs
• Level-planar drawings with few slopes
• Extending Partial Orthogonal Drawings
• On the \(\mathcal{NP}\)-hardness of \textsc{GRacSim drawing} and \(k\)-SEFE problems
• Simultaneous Embedding

This page was built for publication: Simultaneous orthogonal planarity

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