✦ LIBER ✦

Box-Rectangular Drawings of Plane Graphs

✍ Scribed by Md.Saidur Rahman; Shin-ichi Nakano; Takao Nishizeki

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 413 KB
Volume: 37
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1105

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we introduce a new drawing style of a plane graph G called a box-rectangular drawing. It is defined to be a drawing of G on an integer grid such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal line segment or a vertical line segment, and the contour of each face is drawn as a rectangle. We establish a necessary and sufficient condition for the existence of a box-rectangular drawing of G. We also give a linear-time algorithm to find a box-rectangular drawing of G if it exists.

📜 SIMILAR VOLUMES

A Simple Linear Time Algorithm for Prope

A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs

✍ Xin He 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 219 KB

In this paper we introduce a new style of drawing a plane graph G, called proper Ž . box rectangular PBR drawing. It is defined to be a drawing of G such that every vertex is drawn as a rectangle, called a box, each edge is drawn as either a horizontal or a vertical line segment, and each face is dr

Rectilinear drawings of graphs

✍ Carsten Thomassen 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 314 KB

We consider graphs drawn in the plane such that every edge crosses at most one other edge. We characterize, in terms of two forbidden subconfigurations, which of these graphs are equivalent to drawings such that all edges are straight line segments. As a consequence we obtain a complete characteriza

Monotone drawings of planar graphs

✍ János Pach; Géza Tóth 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract Let __G__ be a graph drawn in the plane so that its edges are represented by __x__‐monotone curves, any pair of which cross an even number of times. We show that __G__ can be redrawn in such a way that the __x__‐coordinates of the vertices remain unchanged and the edges become non‐cross

Coupled choosability of plane graphs

✍ Weifan Wang; Ko-Wei Lih 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract A plane graph __G__ is coupled __k__‐choosable if, for any list assignment __L__ satisfying $|{{L}}({{x}})|= {{k}}$ for every ${{x}}\in {{V}}({{G}})\cup {{F}}({{G}})$, there is a coloring that assigns to each vertex and each face a color from its list such that any two adjacent or incid

The plane-width of graphs

✍ Marcin Kamiński; Paul Medvedev; Martin Milanič 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB

Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane-width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane-wid

Performance evaluation of graph drawing

Performance evaluation of graph drawing algorithms

✍ Koji Sumi; Hisatoshi Tanaka; Hiroyuki Ebara; Hideo Nakano 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 857 KB