Rectangle and Square Representations of Planar Graphs

Stefan Felsner ()
Additional contact information
Stefan Felsner: Technische Universität Berlin, Institut für Mathematik

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 213-248 from Springer

Abstract: Abstract In the first part of this survey, we consider planar graphs that can be represented by a dissections of a rectangle into rectangles. In rectangular drawings, the corners of the rectangles represent the vertices. The graph obtained by taking the rectangles as vertices and contacts as edges is the rectangular dual. In visibility graphs and segment contact graphs, the vertices correspond to horizontal or to horizontal and vertical segments of the dissection. Special orientations of graphs turn out to be helpful when dealing with characterization and representation questions. Therefore, we look at orientations with prescribed degrees, bipolar orientations, separating decompositions, and transversal structures. In the second part, we ask for representations by a dissections of a rectangle into squares. We review results by Brooks et al. [The dissection of rectangles into squares. Duke Math J 7:312–340 (1940)], Kenyon [Tilings and discrete Dirichlet problems. Isr J Math 105:61–84 (1998)], and Schramm [Square tilings with prescribed combinatorics. Isr J Math 84:97–118 (1993)] and discuss a technique of computing squarings via solutions of systems of linear equations. Mathematics Subject Classification (2010): 05C10, 05C62, 52C15.

Keywords: Rectangular Drawing; Rectangular Dual; Bipolar Orientation; Contact Segment; Transverse Structure (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_12

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().