arXiv Open Access 2025

Drawing Trees and Cacti with Integer Edge Lengths on a Polynomial-Size Grid

Henry Förster Stephen Kobourov Jacob Miller Johannes Zink

Lihat Sumber

Abstrak

A strengthened version of Harborth's well-known conjecture -- known as Kleber's conjecture -- states that every planar graph admits a planar straight-line drawing where every edge has integer length and each vertex is restricted to the integer grid. Positive results for Kleber's conjecture are known for planar 3-regular graphs, for planar graphs that have maximum degree 4, and for planar 3-trees. However, all but one of the existing results are existential and do not provide bounds on the required grid size. In this paper, we provide polynomial-time algorithms for computing crossing-free straight-line drawings of trees and cactus graphs with integer edge lengths and integer vertex position on polynomial-size integer grids.

Topik & Kata Kunci

cs.CG cs.DM

Penulis (4)

Henry Förster

Stephen Kobourov

Jacob Miller

Johannes Zink

Format Sitasi

APA MLA BibTeX

Förster, H., Kobourov, S., Miller, J., Zink, J. (2025). Drawing Trees and Cacti with Integer Edge Lengths on a Polynomial-Size Grid. https://arxiv.org/abs/2509.04168

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓