Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
GraphMaps: Browsing Large Graphs as Interactive Maps Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Towards Characterizing Graphs with a Sliceable Rectangular Dual

Authors : Vincent Kusters, Bettina Speckmann

Published in: Graph Drawing and Network Visualization

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Let \(\mathcal {G} \) be a plane triangulated graph. A rectangular dual of \(\mathcal {G} \) is a partition of a rectangle R into a set \(\mathcal {R} \) of interior-disjoint rectangles, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge. A rectangular dual is sliceable if it can be recursively subdivided along horizontal or vertical lines. A graph is rectangular if it has a rectangular dual and sliceable if it has a sliceable rectangular dual. There is a clear characterization of rectangular graphs. However, a full characterization of sliceable graphs is still lacking. The currently best result (Yeap and Sarrafzadeh, 1995) proves that all rectangular graphs without a separating 4-cycle are sliceable. In this paper we introduce a recursively defined class of graphs and prove that these graphs are precisely the nonsliceable graphs with exactly one separating 4-cycle.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
next chapter Pixel and Voxel Representations of Graphs
Footnotes
1
Confirmed by Dasgupta and Sur-Kolay, personal communication, 2011-2013.
 
Literature
1.
Ackerman, E., Barequet, G., Pinter, R.Y., Romik, D.: The number of guillotine partitions in d dimensions. Inf. Proces. Letters 98(4), 162–167 (2006)MathSciNetCrossRefMATH
2.
Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G., Ueckerdt, T.: Computing cartograms with optimal complexity. In: SOCG 2012, pp. 21–30 (2012)
3.
de Berg, M., Mumford, E., Speckmann, B.: On rectilinear duals for vertex-weighted plane graphs. Disc. Math. 309(7), 1794–1812 (2009)CrossRefMATH
4.
Bhasker, J., Sahni, S.: A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph. Networks 17(3), 307–317 (1987)MathSciNetCrossRefMATH
5.
Bhattacharya, B., Sur-Kolay, S.: On the family of inherently nonslicible floorplans in VLSI layout design. In: ISCAS 1991, pp. 2850–2853. IEEE (1991)
6.
Buchin, K., Speckmann, B., Verdonschot, S.: Optimizing regular edge labelings. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 117–128. Springer, Heidelberg (2011) CrossRef
7.
Dasgupta, P., Sur-Kolay, S.: Slicible rectangular graphs and their optimal floorplans. ACM Trans. Design Automation of Electronic Systems 6(4), 447–470 (2001)
8.
Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal rectangular layouts. In: SOCG 2009, pp. 267–276 (2009)
9.
Fusy, É.: Transversal structures on triangulations: A combinatorial study and straight-line drawings. Disc. Math. 309(7), 1870–1894 (2009)MathSciNetCrossRefMATH
10.
11.
Kant, G., He, X.: Two algorithms for finding rectangular duals of planar graphs. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 396–410. Springer, Heidelberg (1994)
12.
13.
van Kreveld, M., Speckmann, B.: On rectangular cartograms. Comp. Geom. 37(3), 175–187 (2007)CrossRefMATH
14.
15.
16.
Otten, R.: Efficient floorplan optimization. In: ICCAD’83. vol. 83, pp. 499–502 (1983)
17.
18.
Sur-Kolay, S., Bhattacharya, B.: Inherent nonslicibility of rectangular duals in VLSI floorplanning. In: Kumar, S., Nori, K.V. (eds.) FSTTCS 1988. LNCS, vol. 338, pp. 88–107. Springer, Heidelberg (1988) CrossRef
19.
Szepieniec, A.A., Otten, R.H.: The genealogical approach to the layout problem. In: Proceedings of the 17th Conference on Design Automation, pp. 535–542. IEEE (1980)
20.
Ungar, P.: On diagrams representing maps. J. L. Math. Soc. 1(3), 336–342 (1953)CrossRef
21.
Yao, B., Chen, H., Cheng, C.K., Graham, R.: Floorplan representations: Complexity and connections. ACM Trans. Design Auto. of Elec. Sys. 8(1), 55–80 (2003)
22.
23.
Yeap, K.H., Sarrafzadeh, M.: Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J. Comp. 22(3), 500–526 (1993)MathSciNetCrossRefMATH
Metadata
Title
Towards Characterizing Graphs with a Sliceable Rectangular Dual
Authors
Vincent Kusters
Bettina Speckmann
Copyright Year
2015
Book
Graph Drawing and Network Visualization

Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-27261-0_38

Premium Partner

    Image Credits