Parameterized approaches to orthogonal compaction

DOI10.1007/978-3-031-23101-8_8MaRDI QIDQ6169516zbMATH OpenOpenAlexFDO

Authors Walter Didimo, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Alexander Wolff, Meirav Zehavi

Publication date 14 August 2023

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

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

zbMATH Keywords

compactionorthogonal graph drawingorthogonal representationparameterized complexity

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Orthogonal graph drawings are used in applications such as UML diagrams, VLSI layout, cable plans, and metro maps. We focus on drawing planar graphs and assume that we are given an emph{orthogonal representation} that describes the desired shape, but not the exact coordinates of a drawing. Our aim is to compute an orthogonal drawing on the grid that has minimum area among all grid drawings that adhere to the given orthogonal representation. This problem is called orthogonal compaction (OC) and is known to be NP-hard, even for orthogonal representations of cycles [Evans et al., 2022]. We investigate the complexity of OC with respect to several parameters. Among others, we show that OC is fixed-parameter tractable with respect to the most natural of these parameters, namely, the number of emph{kitty corners} of the orthogonal representation: the presence of pairs of kitty corners in an orthogonal representation makes the OC problem hard. Informally speaking, a pair of kitty corners is a pair of reflex corners of a face that point at each other. Accordingly, the number of kitty corners is the number of corners that are involved in some pair of kitty corners.

Recommendations

• On the complexity of orthogonal compaction
• scientific article; zbMATH DE number 2185601
• A better heuristic for area-compaction of orthogonal representations
• scientific article; zbMATH DE number 1342138
• Hardness of approximate compaction for nonplanar orthogonal graph drawings

Cites work

• Algorithms for plane representations of acyclic digraphs
• Algorithms for Reporting and Counting Geometric Intersections
• An improved fixed-parameter algorithm for one-page crossing minimization
• C-planarity testing of embedded clustered graphs with bounded dual carving-width
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Drawing graphs on few lines and few planes
• Drawing graphs. Methods and models
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• Fundamentals of parameterized complexity
• Grid recognition: classical and parameterized computational perspectives
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• Inapproximability of orthogonal compaction
• Kernelization. Theory of parameterized preprocessing
• Minimum rectilinear polygons for given angle sequences
• On the complexity of orthogonal compaction
• On the parameterized complexity of layered graph drawing
• Orthogonal planarity testing of bounded treewidth graphs
• Parameterized algorithms
• Parameterized algorithms for book embedding problems
• Parameterized Algorithms for Queue Layouts
• Parameterized complexity of 1-planarity
• Parameterized complexity of graph planarity with restricted cyclic orders
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Subexponential-time and FPT algorithms for embedded flat clustered planarity
• Testing upward planarity of partial 2-trees
• Turn-regularity and optimal area drawings of orthogonal representations
• Upward book embeddings of st-graphs
• Upward drawings of triconnected digraphs.

Cited in

(3)

• A framework for 1-D compaction with forbidden region avoidance
• scientific article; zbMATH DE number 2185601 (Why is no real title available?)
• Drawn tree decomposition: new approach for graph drawing problems

This page was built for publication: Parameterized approaches to orthogonal compaction

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