Trimming of graphs, with application to point labeling

DOI10.1007/S00224-009-9184-8zbMath1225.05212OpenAlexW2157796928MaRDI QIDQ1959389

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

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 graphsmap labelingpolynomial-time approximation schemesdomino treewidthlayer bandwidthpoint-feature label placementsliding labelstrimming weighted graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22)

Related Items (2)

A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Minimum point-overlap labelling*

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

This page was built for publication: Trimming of graphs, with application to point labeling