Open AccessExternal Memory Algorithms for Outerplanar Graphs
Author(s) -
Anil Maheshwari,
Norbert Zeh
Publication year - 1999
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-66916-7
DOI - 10.1007/3-540-46632-0_31
Subject(s) - embedding , combinatorics , outerplanar graph , graph , matching (statistics) , algorithm , computer science , mathematics , discrete mathematics , pathwidth , line graph , statistics , artificial intelligence
We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadth-first search (BFS) and depth-first search (DFS) in outerplanar graphs, and finding a 2/3-separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O(perm(N)) I/Os, as all these problems have linear time solutions in internal memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom