Schematization of road networks
- 1 June 2001
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
We study the problem of computing schematized versions of network maps , like railroad maps. Every path of the schematized map has two or three links with restricted orientations, and topologically, the schematized map must be equivalent to the input map. Our approach applies to several types of schematizations, and certain additional constraints can be added. In the general case our algorithm takes $O(n\log^3n)$ time, and when all paths in the input are monotone in some (not necessarily the same) direction, it runs in $O(n\log n)$ time.
Keywords
This publication has 5 references indexed in Scilit:
- Computational GeometryPublished by Springer Nature ,1997
- Computing and Verifying Depth OrdersSIAM Journal on Computing, 1994
- On Embedding a Graph in the Grid with the Minimum Number of BendsSIAM Journal on Computing, 1987
- Single bend wiringJournal of Algorithms, 1986
- Basic Concepts of Algebraic TopologyPublished by Springer Nature ,1978