Trimming of graphs, with application to point labeling

DOI10.1007/s00224-009-9184-8zbMath1225.05212MaRDI QIDQ1959389

Erlebach, Thomas, Klaus Jansen, Alexander Wolff, Torben Hagerup, Moritz Minzlaff

Publication date: 6 October 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9184-8

zbMATH Keywords

planar graphs; map labeling; polynomial-time approximation schemes; domino treewidth; layer bandwidth; point-feature label placement; sliding labels; trimming weighted graphs

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C20: Directed graphs (digraphs), tournaments

05C22: Signed and weighted graphs

Related Items

A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem

Cites Work

• Unnamed Item
• Unnamed Item
• A new approximation algorithm for labeling points with circle pairs
• \(\epsilon\)-nets and simplex range queries
• A partial k-arboretum of graphs with bounded treewidth
• Label placement by maximum independent set in rectangles
• Point labeling with sliding labels
• Polynomial time algorithms for three-label point labeling.
• Labeling points with weights
• Graph minors. II. Algorithmic aspects of tree-width
• Approximation schemes for covering and packing problems in image processing and VLSI
• Complexity Results for Bandwidth Minimization
• Approximation algorithms for NP-complete problems on planar graphs
• LABELING POINTS WITH CIRCLES
• Some results on tree decomposition of graphs