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

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
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

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{3cabb19c7a2d4ea0a3ceb81580d81192,

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

AN - SCOPUS:84958044964

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