A simple linear time algorithm for proper box rectangular drawings of plane graphs

Xin He

doi:10.1007/3-540-44634-6_22

A simple linear time algorithm for proper box rectangular drawings of plane graphs

Xin He

Department of Computer Science and Engineering

University at Buffalo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper we introduce a new drawing style of 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 drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem.

Original language	English
Title of host publication	Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings
Editors	Frank Dehne, Jorg-Rudiger Sack, Roberto Tamassia
Publisher	Springer Verlag
Pages	234-245
Number of pages	12
ISBN (Print)	3540424237, 9783540424239
DOIs	https://doi.org/10.1007/3-540-44634-6_22
State	Published - 2001
Event	7th International Workshop on Algorithms and Data Structures, WADS 2001 - Providence, United States Duration: Aug 8 2001 → Aug 10 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2125

Conference

Conference	7th International Workshop on Algorithms and Data Structures, WADS 2001
Country/Territory	United States
City	Providence
Period	08/8/01 → 08/10/01

Access to Document

10.1007/3-540-44634-6_22

Cite this

He, X. (2001). A simple linear time algorithm for proper box rectangular drawings of plane graphs. In F. Dehne, J.-R. Sack, & R. Tamassia (Eds.), Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings (pp. 234-245). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2125). Springer Verlag. https://doi.org/10.1007/3-540-44634-6_22

He, Xin. / A simple linear time algorithm for proper box rectangular drawings of plane graphs. Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Roberto Tamassia. Springer Verlag, 2001. pp. 234-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6e200e929ed143018e08f1cc3d0e0ae2,

title = "A simple linear time algorithm for proper box rectangular drawings of plane graphs",

abstract = "In this paper we introduce a new drawing style of 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 drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem.",

author = "Xin He",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 7th International Workshop on Algorithms and Data Structures, WADS 2001 ; Conference date: 08-08-2001 Through 10-08-2001",

year = "2001",

doi = "10.1007/3-540-44634-6\_22",

language = "English",

isbn = "3540424237",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "234--245",

editor = "Frank Dehne and Jorg-Rudiger Sack and Roberto Tamassia",

booktitle = "Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings",

address = "Germany",

}

He, X 2001, A simple linear time algorithm for proper box rectangular drawings of plane graphs. in F Dehne, J-R Sack & R Tamassia (eds), Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2125, Springer Verlag, pp. 234-245, 7th International Workshop on Algorithms and Data Structures, WADS 2001, Providence, United States, 08/8/01. https://doi.org/10.1007/3-540-44634-6_22

A simple linear time algorithm for proper box rectangular drawings of plane graphs. / He, Xin.
Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Roberto Tamassia. Springer Verlag, 2001. p. 234-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2125).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A simple linear time algorithm for proper box rectangular drawings of plane graphs

AU - He, Xin

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - In this paper we introduce a new drawing style of 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 drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem.

AB - In this paper we introduce a new drawing style of 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 drawn as a rectangle. We establish necessary and sufficient conditions for G to have a PBR drawing. We also give a simple linear time algorithm for finding such drawings. The PBR drawing is closely related to the box rectangular (BR) drawing defined by Rahman, Nakano and Nishizeki [17]. Our method can be adapted to provide a new algorithm for solving the BR drawing problem.

UR - https://www.scopus.com/pages/publications/84958044964

U2 - 10.1007/3-540-44634-6_22

DO - 10.1007/3-540-44634-6_22

M3 - Conference contribution

SN - 3540424237

SN - 9783540424239

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 234

EP - 245

BT - Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Tamassia, Roberto

PB - Springer Verlag

T2 - 7th International Workshop on Algorithms and Data Structures, WADS 2001

Y2 - 8 August 2001 through 10 August 2001

ER -

He X. A simple linear time algorithm for proper box rectangular drawings of plane graphs. In Dehne F, Sack JR, Tamassia R, editors, Algorithms and Data Structures - 7th International Workshop, WADS 2001, Proceedings. Springer Verlag. 2001. p. 234-245. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44634-6_22

A simple linear time algorithm for proper box rectangular drawings of plane graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this