@inbook{a59f5f0696ba40448352e73b30ac2489,
title = "Compact visibility representation and straight-line grid embedding of plane graphs",
abstract = "We study the properties of Schnyder's realizers and canonical ordering trees of plane graphs. Based on these newly discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a visibility representation with height at most ⌈15n/16⌉. This improves the previous best bound of n-1. The drawing can be obtained in linear time. Second, we show that every plane graph G has a straight-line grid embedding on an (n - Δ0-1) x (n-Δ0-1) grid, where Δ0 is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of (n-1) x (n-1). This embedding can also be found in O(n) time.",
author = "Huaming Zhang and Xin He",
year = "2003",
doi = "10.1007/978-3-540-45078-8\_43",
language = "English",
isbn = "3540405453",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "493--504",
editor = "Frank Dehne and Jorg-Rudiger Sack and Michiel Smid",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}