×

Single bend wiring on surfaces. (English) Zbl 1004.68002

Summary: The following problem of rectilinear routing is studied: given pairs of points on a surface and a set of permissible orthogonal paths joining them, whether is it possible to choose a path for each pair avoiding all intersections. We prove that if each pair has one or two possible paths to join it, then the problem is solvable in quadratic time, and otherwise it is NP-complete. From that result, we will obtain that the problem of finding a surface of minimum genus on which the wires can be laid out with only one bend is NP-hard.

MSC:

68M07 Mathematical problems of computer architecture
68M99 Computer system organization

Software:

BEAVER
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batini, C.; Nardelli, E.; Tamassia, R., A layout algorithm for data-flow diagrams, IEEE Trans. Software Eng., SE-12, 4, 538-546 (1986)
[2] Batini, C.; Talamo, M.; Tamassia, R., Computer aided layout of entity-relationship diagrams, J. Systems Software, 4, 163-173 (1984)
[3] T.C. Biedl, Optimal orthogonal drawings of triconnected plane graphs, Proceedings of the SWAT’96, Lecture Notes in Computer Science, Vol. 1097, Springer, Berlin, 1996, pp. 333-344.; T.C. Biedl, Optimal orthogonal drawings of triconnected plane graphs, Proceedings of the SWAT’96, Lecture Notes in Computer Science, Vol. 1097, Springer, Berlin, 1996, pp. 333-344.
[4] Cohoon, J. P.; Heck, P. L., BEAVER: a computational-geometry-based tool for switchbox routing, IEEE Trans. Comput.-Aided Des. Integrated Circuits Systems, 7, 6, 684-697 (1988)
[5] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SICOMP, 5, 691-703 (1976) · Zbl 0358.90021
[6] M.A. Garrido, A. Márquez, Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard, in: G. DiBattista (Ed.), Graph Drawing, Proceedings of the GD’97, Lecture Notes in Computer Science, Vol. 1353, Springer, Berlin, 1998, pp. 124-133.; M.A. Garrido, A. Márquez, Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard, in: G. DiBattista (Ed.), Graph Drawing, Proceedings of the GD’97, Lecture Notes in Computer Science, Vol. 1353, Springer, Berlin, 1998, pp. 124-133.
[7] Hsu-Chun, Y., On multilinear single bend wirability, IEEE Trans. Comput.-Aided Des. Integrated Circuits Systems, 13, 6, 822-826 (1994)
[8] Lengauer, T., Combinatorial Algorithms for Integrated Circuit Layout (1990), Wiley: Wiley New York · Zbl 0709.68039
[9] Liu, Y.; Morgana, A.; Simeone, B., General theoretical results on rectilinear embeddability of graphs, Acta Math. Appl. Sinica, 7, 187-192 (1991) · Zbl 0732.05021
[10] Liu, Y.; Morgana, A.; Simeone, B., A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Discrete Appl. Math., 81, 69-91 (1998) · Zbl 0912.68153
[11] Raghavan, R.; Cohoon, J.; Sahni, S., Single bend wiring, J. Algorithms, 7, 232-257 (1986) · Zbl 0606.94019
[12] Tamassia, R., On embedding a graph in the grid with the minimum number of bends, SIAM J. Comput., 16, 421-444 (1987) · Zbl 0654.68090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.