Modifying orthogonal drawings for label placement

DOI10.3390/A9020022MaRDI QIDQ1736777zbMATH OpenOpenAlexFDO

Authors Konstantinos G. Kakoulis, Ioannis G. Tollis

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a9020022

zbMATH Keywords

automated label placementedge labelinggraph drawinggraph labelingNP-hardorthogonal drawings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Summary: In this paper, we investigate how one can modify an orthogonal graph drawing to accommodate the placement of overlap-free labels with the minimum cost (\textit{i.e.}, minimum increase of the area and preservation of the quality of the drawing). We investigate computational complexity issues of variations of that problem, and we present polynomial time algorithms that find the minimum increase of space in one direction, needed to resolve overlaps, while preserving the orthogonal representation of the orthogonal drawing when objects have a predefined partial order.

Recommendations

• scientific article; zbMATH DE number 2084273
• scientific article; zbMATH DE number 1974108
• Orthogonal drawings of graphs with vertex and edge labels
• A combinatorial approach to orthognal placement problems
• Three rules suffice for good label placement

Cites work

• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A UNIFIED APPROACH TO AUTOMATIC LABEL PLACEMENT
• Algorithms for area-efficient orthogonal drawing
• Algorithms for drawing graphs: An annotated bibliography
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1500674 (Why is no real title available?)
• Interactive orthogonal graph drawing
• Network flows. Theory, algorithms, and applications.
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the complexity of the Edge Label Placement problem
• Orthogonal drawings of graphs with vertex and edge labels

Cited in

(3)

• Orthogonal drawings of graphs with vertex and edge labels
• Placing arrows in directed graph drawings
• scientific article; zbMATH DE number 2084273 (Why is no real title available?)

This page was built for publication: Modifying orthogonal drawings for label placement

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