✦ LIBER ✦

Monotone drawings of planar graphs

✍ Scribed by János Pach; Géza Tóth

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 92 KB
Volume: 46
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10168

No coin nor oath required. For personal study only.

✦ Synopsis

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‐crossing straight‐line segments. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 39–47, 2004

📜 SIMILAR VOLUMES

An algorithm for drawing planar graphs

✍ Bor Plestenjak 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s

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

A Framework for Drawing Planar Graphs wi

A Framework for Drawing Planar Graphs with Curves and Polylines

✍ Michael T. Goodrich; Christopher G. Wagner 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 204 KB

We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings, including aspect ratio, vertex resolution, edge length, edge separation, and edge curvature, as well

Moments of graphs in monotone families

✍ Zoltán Füredi; André Kündgen 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract The __k__th __moment__ of the degree sequence __d__~1~ ≥ __d__~2~ ≥ …__d__~n~ of a graph __G__ is $\mu \_k(G)={1\over n}{\sum}{d\_i^k}$. We give asymptotically sharp bounds for μ~k~(__G__) when __G__ is in a monotone family. We use these results for the case __k__ = 2 to improve a resul

Box-Rectangular Drawings of Plane Graphs

✍ Md.Saidur Rahman; Shin-ichi Nakano; Takao Nishizeki 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 413 KB

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, a

-constructibility of planar graphs

✍ C. M. Mynhardt; I. Broere 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 386 KB

## Abstract In this paper, the concept of the 𝒢‐constructibility of graphs is introduced and investigated with particular reference to planar graphs. It is conjectured that the planar graphs are minimally __N__‐constructible, where __N__ is a finite set of graphs and an infinite set 𝒢 is obtained s