| Home | Organizers | Proceedings Editors | Proceedings Contributors | Search | | ||
|
|
|||
|
||||
|
|
||||
| Title: | REPRESENTING SERIES-PARALLEL GRAPHS AS INTERSECTION GRAPHS OF LINE SEGMENTS IN THREE DIRECTIONS | |
| DOI No: | 10.1142/9781860948534_0003 | |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 32-36) | |
| Author(s): | MANUEL BODIRSKY
Department of Algorithms and Complexity, Institute for Computer Science, Humboldt University, Berlin, Germany CORNELIA DANGELMAYR Institute for Mathematics II, Free University, Berlin, Germany JAN KÁRA Supported by project 1M0021620808 of the Ministry of Education of the Czech Republic. Part of the work was done while the author has been visiting Humboldt University, with the support by a Marie Curie Fellowship of the European Graduate Program "Combinatorics, Geometry, and Computation" under contract number HPMT-CT-2001-00282. Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic |
|
| Abstract: | In this paper we show that series-parallel graphs (i.e., K4-minor free graphs) can be represented as contact intersection graphs of straight-line segments in three directions. Moreover, in our representations no two segments of the same direction intersect. | |
| Full Text: | View full text in PDF format (256KB) | |
| TOC: | Back to Table of Contents | |
|
||