Orthogonal graph drawing with inflexible edges

DOI10.1007/978-3-319-18173-8_4MaRDI QIDQ2947010zbMATH OpenOpenAlexFDO

Authors Thomas Bläsius, Ignaz Rutter, Sebastian B. C. Lehmann

Publication date 21 September 2015

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

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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) Flows in graphs (05C21)

Abstract: We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge $e$ a natural number $mathrmflex(e)$, its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge $e$ has at most $mathrmflex(e)$ bends. It is known that FlexDraw is NP-hard if $mathrmflex(e)=0$ for every edge $e$. On the other hand, FlexDraw can be solved efficiently if $mathrmflex(e)ge1$ and is trivial if $mathrmflex(e)ge2$ for every edge $e$. To close the gap between the NP-hardness for $mathrmflex(e)=0$ and the efficient algorithm for $mathrmflex(e)ge1$, we investigate the computational complexity of FlexDraw in case only few edges are inflexible (i.e., have flexibility~$0$). We show that for any $varepsilon>0$ FlexDraw is NP-complete for instances with $O(n^{v}arepsilon)$ inflexible edges with pairwise distance $Omega(n^{1-varepsilon})$ (including the case where they induce a matching). On the other hand, we give an FPT-algorithm with running time $O(2^{k}cdotncdot{T}_{mathrmflow}(n))$, where $T_{mathrmflow}(n)$ is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and $k$ is the number of inflexible edges having at least one endpoint of degree 4.

Recommendations

• Orthogonal graph drawing with inflexible edges
• Orthogonal graph drawing with flexibility constraints
• Orthogonal graph drawing with flexibility constraints
• Optimal orthogonal graph drawing with convex bend costs
• Optimal Orthogonal Graph Drawing with Convex Bend Costs

Cites work

• A better heuristic for orthogonal graph drawings
• Accelerated bend minimization
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the computational complexity of upward and rectilinear planarity testing
• On-line maintenance of triconnected components with SPQR-trees
• Optimal Orthogonal Graph Drawing with Convex Bend Costs
• Orthogonal graph drawing with flexibility constraints
• Orthogonal graph drawing with inflexible edges
• Spirality and Optimal Orthogonal Drawings

Cited in

(11)

• Interactive orthogonal graph drawing
• Orthogonal layout with optimal face complexity
• Optimal orthogonal graph drawing with convex bend costs
• Relating bends and size in orthogonal graph drawings
• Orthogonal graph drawing with flexibility constraints
• Orthogonal graph drawing with flexibility constraints
• Orthogonal graph drawing with inflexible edges
• Orthogonal graph drawing with inflexible edges
• Orthogonal layout with optimal face complexity
• Orthogonal-ordering constraints are tough
• Orthogonal Drawings of Plane Graphs Without Bends

This page was built for publication: Orthogonal graph drawing with inflexible edges

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