Orthogonal Drawings for Plane Graphs with Specified Face Areas

Autor:	Hiroshi Nagamochi, Akifumi Kawaguchi
Rok vydání:	2007
Předmět:	Combinatorics symbols.namesake Graph drawing Outerplanar graph symbols Slope number Dominance drawing Crossing number (graph theory) Lattice graph 1-planar graph Mathematics Planar graph
Zdroj:	Lecture Notes in Computer Science ISBN: 9783540725039 TAMC
DOI:	10.1007/978-3-540-72504-6_53
Popis:	We consider orthogonal drawings of a plane graph G with specified face areas. For a natural number k, a k-gonal drawing of G is an orthogonal drawing such that the outer cycle is drawn as a rectangle and each inner face is drawn as a polygon with at most k corners whose area is equal to the specified value. In this paper, we show that several classes of plane graphs have a k-gonal drawing with bounded k; A slicing graph has a 10-gonal drawing, a rectangular graph has an 18-gonal drawing and a 3-connected plane graph whose maximum degree is 3 has a 34- gonal drawing. Furthermore, we showed that a 3-connected plane graph G whose maximum degree is 4 has an orthogonal drawing such that each inner facial cycle c is drawn as a polygon with at most 10pc +34 corners, where pc is the number of vertices of degree 4 in the cycle c.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::0fe7d602029efe614c96247603c5a613 https://doi.org/10.1007/978-3-540-72504-6_53 Zobrazit plný text záznamu