[Michael Kaufmann] [Publications]
- Still under construction -
Extended abstracts of journal publications usually also appeared in conference proceedings, extra citations are omitted. Furthermore, we do not mention technical reports as well as abstracts for workshops. The papers are ordered according to their origination time, not according to their appearance time.
Some of the recent technical reports (+ps-files) are added at the end.


Journal Publications


M.Kaufmann, K.Mehlhorn: ``Routing through a Generalized Switchbox'', Journal of Algorithms 7, pp. 510-531, 1986.

M.Kaufmann: ``A Linear-Time Algorithm for Routing in a Convex Grid'', IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 180-184, 1990.

M.Kaufmann, K.Mehlhorn: ``On Local Routing of Two-Terminal Nets'', Journal of Combinatorial Theory, Series B, pp. 33-72, 1992.

S.Gao, M.Kaufmann: ``Channel Routing of Multiterminal Nets'', Journal of the ACM, pp. 791-818, 1994.

M.Kaufmann, K. Mehlhorn: ``Routing problems in grid graphs'', in Algorithms and Combinatorics, Vol. 9, (eds. Korte, Lov'asz, Prömel, Schrijver: ) "Paths, Flows and VLSI-Layout", Springer-Verlag, 1991.

M.Kaufmann, P. Molitor: ``Minimal stretching of a layout to ensure 2-layer wirability'', Integration -- The VLSI Journal, pp. , 1991.

M.Kaufmann, K.Mehlhorn: ``A linear-time algorithm for the Homotopic Routing Problem in Grid Graphs'', SIAM Journal of Computing, pp. 227-246 (1994).

M.Kaufmann, F.M.Maley: ``Parity Conditions for Homotopic Knock-knee Routing'', Algorithmica, pp. 47-63, 1993.

M.Kaufmann, F.M.Maley: ``Computing Congestion during One-dimen-sional Homotopic Compaction'', to appear in Journal of Algorithms.

M.Kaufmann, G. Klär: ``Routing in Polygons without Rectilinearly Visible Corners'', Information & Computation, pp. 218-263, 1993.

H.Alt, R.Fleischer, M.Kaufmann, K.Mehlhorn, S.Näher, S.Schirra, Ch.Uhrig: ``Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures'', Algorithmica, pp. 391-406, 1992.

M.Formann, T.Hagerup, J.Haralambides, M.Kaufmann, F.T.Leighton, A.Simvonis, E.Welzl, G.Wo eginger: ``Drawing Graphs in the Plane with High Resolution'', SIAM Journal of Computing, Vol.22, pp. 1035-152, 1993.

M.Kaufmann, S.Gao and K.Thulasiraman: ``On Steiner Minimal Trees in Grid Graphs and Its Application to Homotopic Routing '', Journal of Circuits, Systems and Computers, Vol. 6, No. 1, pp. 1-13, 1996.

M.Kaufmann, H.Schröder, J.Sibeyn: ``Asymptotically Optimal and Practical Routing on Reconfigurable Meshes'', Special Issue of 'Parallel Processing Letters', Vol. 5(1) , pp. 81-95, 1995.

M.Kaufmann, J.F.Sibeyn: ``Randomized Multi-packet Routing and Sorting on Meshes'', Algorithmica 17, pp. 224-244, 1997.

B.Chlebus, M.Kaufmann, J.F.Sibeyn: ``Deterministic Permutation Routing on Meshes'', Journal of Algorithms 22, pp. 111-141, 1997.

M. Kaufmann, R. Raman, J.F. Sibeyn, `Randomized Routing on Meshes with Buses,' Algorithmica 18, pp. 417-444, 1997.

Th.Biedl, G.Kant, M.Kaufmann: ``On Triangulating Planar Graphs under the Four-Connectivity Constraint'', Algorithmica, 19(4), pp. 427-446, 1997.

U. Fößmeier, M. Kaufmann, A. Zelikovsky: ``Faster Approximation Algorithms for the Rectilinear Steiner Problem'', Discrete & Computational Geometry 18, pp. 93-109, 1997.

M. Kaufmann, U. Meyer, J. Sibeyn: ``Towards Practical Permutation Routing on Meshes'', to appear in ????, 1997

Kaufmann, M., U. Meyer, J.F. Sibeyn, ``Matrix Transpose on Meshes: Theory and Practice,'' Computers and Artificial Intelligence, Vol. 16, pp. 107-140, 1997.


Publications in Conference Proceedings


M. Kaufmann: ``Nearly tight bounds for the longest edge of a tree in a VLSI Layout'', Proc. of 9th Colloquium on Trees in Algebra and Programming, Cambridge University Press, pp. 169-179, 1984.

S. Gao, M.Jerrum, M.Kaufmann, K.Mehlhorn, W.Rülling, Ch.Storb: ``On Continuous Homotopic One-Layer Routing'', Proc. of 4th ACM Symposium on Computational Geometry, pp. 392-402, 1988.

M.Kaufmann, I.G. Tollis: ``Channel routing with short wires'', Proc. of 3rd Aegean Workshop of Computing, LNCS 319, pp. 226-236, Springer-Verlag, 1988.

S.Gao, M.Kaufmann, F.M.Maley: ``Advances in homotopic layout compaction'', Proc. of ACM Symposium on Parallel Algorithms and Architectures, pp. 273-282, 1989.

M.Kaufmann, G. Klär: ``Routing Around a Rectangle --The General Case--'', Proc. Workshop on Combinatorial Optimization, Barbados 1989.

M.Kaufmann: ``Allowing Overlaps makes Switchbox Layouts Nice'', Proc. 2nd IEEE Symposium on Parallel and Distributed Processing, pp. 267-274, 1990.

M.Kaufmann, P.Molitor, W.Vogelgesang: ``Performance Driven $k$-Layer Wiring'', Proc. 9th Symposium on Theoretical Aspects of Computer Science (STACS'92), LNCS 775, pp. 237-248, Springer-Verlag, 1992.

F.Hoffmann, M.Kaufmann: ``On the Rectilinear Art Gallery Problem -- Algorithmic Aspects'', Proc. Workshop on Graphtheoretic Concepts in Computer Science (WG'90), LNCS 484, Springer-Verlag, 1990.

M.Kaufmann, I.G. Tollis: ``Switchbox routing for multiterminal nets in Manhattan mode'', Proc. 27th Annual Allerton Conference, pp. 301-309, 1989.

P.Eklund, M.Kaufmann: ``Hierarchical Wiring in Multigrids'', Proc. Joint Conference on Vector and Parallel Processing CONPAR'90, Zürich 1990.

P. Eklund, M.Kaufmann: ``Canonical Mapping in Variable Architectures'', Technical Report 1990, Postersession von `2nd European Distributed Memory Computing Conference (EDMCC2)', 1991.

F.Hoffmann, M.Kaufmann, K.Kriegel: ``The Art Gallery Theorem for Polygons with Holes'', Proc. 32nd Symposium on Foundations of Computer Science (FOCS'91), pp. 39-48, IEEE, 1991.

M.Kaufmann, G. Klär: ``A faster algorithm for the edge-disjoint path problem in planar graphs'' Proc. 2nd SIGAL Conference on Algorithms, Taiwan, LNCS, 1991.

M.Kaufmann, R.Rajasekaran, J.F.Sibeyn: ``Matching the Bisection bound for Routing and Sorting on the Mesh'', Proc. 4th Symposium on Parallel Algorithms and Architectures SPAA, pp. 31-40, ACM, 1992.

M.Kaufmann, J.F.Sibeyn: ``Optimal multi-packet routing on the torus'', Proc. 3th Scandinavian Workshop on Algorithm Theory SWAT, LNCS 621, pp. 118-129, Springer-Verlag, 1992.

M.Kaufmann, J.F.Sibeyn: ``Deterministic Routing on Circular Arrays'', Proc. 4th Symposium on Parallel and Distributed Processing (SPDP'92), pp. 376-383, IEEE, 1992.

U. Fößmeier, M. Kaufmann: ``An Approach for Bend-Minimal Upward Drawings'', Proc. Alcom-Workshop on Graph-Drawing (GD'93), pp. 27-29, 1993.

M.Kaufmann, J.F.Sibeyn, T.Suel: ``Derandomizing Algorithms for Routing and Sorting on Meshes'', Proc. 5th Symposium on Discrete Algorithms (SODA'94), pp. 669-679, ACM-SIAM, 1994.

J.F.Sibeyn, M.Kaufmann: ``Deterministic 1-k Routing on Meshes (with Applications to Worm-Hole Routing)'', Proc. 11th Symposium on Theoretical Aspects of Computer Science (STACS'94), LNCS 775, pp. 237-248, Springer-Verlag, 1994.

B.Chlebus, M.Kaufmann, J.F.Sibeyn: ``Routing on Meshes with Small Queues'', Proc. 8th Mathematical Foundations of Computer Science (MFCS'94), LNCS 841, pp. 597-607, Springer-Verlag, 1994.

M.Kaufmann, H.Lauer, H. Schröder: ``Fast Deterministic Hot-Potato Routing on Meshes'', Proc. 5th Symposium on Algorithms and Computation (ISAAC'94). LNCS 834, pp. 333-341, Springer-Verlag, 1994.

P.Berman, U.Fößmeier, M.Karpinski, M.Kaufmann, A.Zelikovsky: ``Approaching the 5/4 -- Approximation for Rectilinear Steiner Trees'', Proc. 2nd European Symposium on Algorithms (ESA'94), LNCS, pp. 60-71, Springer-Verlag, 1994.

U.Fößmeier, M.Kaufmann: ``On Bend-Minimum Upward Drawing of Directed Planar Graphs'', Proc. DIMACS-Workshop on Graph-Drawing (GD'94), LNCS 894, pp. 52-63, Springer-Verlag, 1995.

J.F.Sibeyn, M.Kaufmann: ``Solving Cheap Graph Problems on Meshes '', Proc. 9th Mathematical Foundations of Computer Science (MFCS'95), LNCS 969, pp. 412--422, Springer-Verlag, 1995.

M.Kaufmann, J.F.Sibeyn, T. Suel: ``Beyond the Bisection Bound: Fast Ranking and Counting on Meshes'', Proc. 3rd European Symposium on Algorithms (ESA'95), LNCS 979, pp. 75-88, Springer-Verlag, 1995.

U.Fößmeier, M.Kaufmann: ``Drawing High Degree Graphs with Low Bend Numbers'', Proc. 4th Symposium on Graph Drawing (GD'95), LNCS 1011, pp. , Springer-Verlag, 1995.

U. Fößmeier, G. Kant and M. Kaufmann: ``2-Visibility Drawings of Planar Graphs'', Proc. 5th Symposium on Graph Drawing (GD'96), LNCS 1190, pp. 155-168, 1996.

U. Fößmeier, M.Kaufmann: ``Nice Drawings of Planar Bipartite Graphs '', Proc. 3rd Italian Conference on Algorithms and Complexity, LNCS 1203, pp. 122-134, 1997.

Sibeyn, J.F., M. Kaufmann, `BSP-Like External-Memory Computation,' Proc. 3rd Italian Conference on Algorithms and Complexity, LNCS 1203, pp. 229-240, 1997.

U. Fößmeier and M. Kaufmann: ``On Exact Solutions for the Rectilinear Steiner Problem'', Postersession of 13th ACM Symposium of Computational Geometry, pp. 1997. .

Th.Biedl, M.Kaufmann: ``Area-Efficient Static and Incremental Graph Drawings'', Proc. 5th European Symposium on Algorithms (ESA'97), LNCS 1284, pp. 37-52, Springer-Verlag, 1997.

U. Fößmeier and M. Kaufmann: ``Solving rectilinear Steiner tree problems exactly in theory and practice'', Proc. 5th European Symposium on Algorithms (ESA'97), LNCS 1284, pp. 171-185, Springer-Verlag, 1997.

U. Fößmeier, M. Kaufmann: ``Algorithms and Area Bounds for Nonplanar Orthogonal Drawings'', Proc. 6th Symposium on Graph Drawing (GD'97), LNCS 1353, pp. 134-145, 1997.

Th. Biedl, M. Kaufmann, P. Mutzel: ``Drawing Planar Partitions II: HH-Drawings'', Proc. 24th Workshop on Graphtheoretic Concepts in Computer Science (WG'98), LNCS 1517, pp. 124-136, 1998.

U. Fößmeier, C. Hess, M. Kaufmann: ``On Imporving Orthogonal Drawings: The 4M - Algorithm'', Proc. 8th Symposium on Graph Drawing (GD'98), LNCS 1547, pp. 125-137, 1998.

B. Steckelbach, T. Bubeck, U. Fößmeier, M. Kaufmann, M. Ritt, W. Rosenstiel: ``Visualization of Parallel Execution Graphs'', Proc. 8th Symposium on Graph Drawing (GD'98), LNCS 1547, pp. 403-412, 1998.

M. Kaufmann, R. Wiese: ``Mapping vertices to points: Few Bends suffice'', Proc. 9th Symposium on Graph Drawing (GD'99), LNCS 1731, pp.\ 165-174, 1999.

M. Eiglsperger, U. Fößmeier, M. Kaufmann: ``Orthogonal Graph Drawing with Constraints'', Proc. 11th Symposium on Discrete Algorithms (SODA'00), ACM-SIAM, pp.\ 3-11, 2000

M. Eiglsperger, M. Kaufmann: ``Visualization of Biodegradation Pathways in the UM-BDD'', Posterproceedings RECOMB 2001, Currents in Computational Molecular Biology 2001, Les Publications CRM, Montreal, pp. 223-224, 2001.

E. Adebiyi, T. Jiang, M. Kaufmann: ``An Efficient Algorithm for Finding Short Approximate Non-tandem Repeats'', Proc. Intelligent Systems of Molecular Biology (ISMB'01), in Bioinformatics, pp. XX, 2001. M. Eiglsperger, M. Kaufmann: ``An Approach for Mixed Upward Planarization'',< /A> Proc. 7th International Workshop on Algorithms and Data Structures (WADS'01), LNCS, pp.\ 352-364, 2001.

M. Schmollinger, M. Kaufmann: ``kNUMA: Model for Clusters in SMP-Machines'',< /A> Proc. Parallel Processing and Applied Mathematics (PPAM 2001), LNCS, to appear. ``Visualization of Biodegradation Pathways in the UM-BDD'', Posterproceedings RECOMB 2001, Currents in Computational Molecular Biology 2001, Les Publications CRM, Montreal, pp. 223-224, 2001.

E. Adebiyi, T. Jiang, M. Kaufmann: ``An Efficient Algorithm for Finding Short Approximate Non-tandem Repeats'', Proc. Intelligent Systems of Molecular Biology (ISMB'01), in Bioinformatics, pp. XX, 2001. M. Eiglsperger, M. Kaufmann: ``An Approach for Mixed Upward Planarization'',< /A> Proc. 7th International Workshop on Algorithms and Data Structures (WADS'01), LNCS, pp.\ 352-364, 2001.

M. Schmollinger, M. Kaufmann: ``kNUMA: Model for Clusters in SMP-Machines'',< /A> Proc. Parallel Processing and Applied Mathematics (PPAM 2001), LNCS, to appear.

M. Eiglsperger, M. Kaufmann: ``Fast Compaction for Orthogonal Drawings with Vertices of Prescribed Size'',< /A> Proc. 11th Symposium on Graph Drawing (GD'01), LNCS, to appear 2002, 1999.

R.\ Wiese, M. Eiglsperger, M. Kaufmann: ``yFiles: Visualization and Automatic Layout of Graphs'',< /A> Proc. 11th Symposium on Graph Drawing (GD'01), LNCS, to appear 2002, 1999.

B. Diebold, M. Kaufmann: ``Usage-based Visualization of Web Localities'',< /A> Proc. Information Visualisation 2001, (InVis.au), Australian Computer Society, pp. 159 -- 164. M. Schmollinger, M. Kaufmann: ``Algorithms of SMP-Clusters Dense Matrix-Vector Multiplication'',< /A> Proc. Workshop on Advances in Parallel and Distributed Computational Models (APDCM'02), to appear.

M. Eiglsperger, M. Kaufmann: ``Fast Compaction for Orthogonal Drawings with Vertices of Prescribed Size'',< /A> Proc. 11th Symposium on Graph Drawing (GD'01), LNCS, to appear 2002, 1999.

R.\ Wiese, M. Eiglsperger, M. Kaufmann: ``yFiles: Visualization and Automatic Layout of Graphs'',< /A> Proc. 11th Symposium on Graph Drawing (GD'01), LNCS, to appear 2002, 1999.

B. Diebold, M. Kaufmann: ``Usage-based Visualization of Web Localities'',< /A> Proc. Information Visualisation 2001, (InVis.au), Australian Computer Society, pp. 159 -- 164. M. Schmollinger, M. Kaufmann: ``Algorithms of SMP-Clusters Dense Matrix-Vector Multiplication'',< /A> Proc. Workshop on Advances in Parallel and Distributed Computational Models (APDCM'02), to appear.


% Recent technical reports

%
% % P.Berman, U.Fößmeier, M.Karpinski, M.Kaufmann, A.Zelikovsky: % ``Approaching the 5/4 -- Approximation for Rectilinear Steiner Trees'', % Technical Report, WSI-94-06.

% % U.Fößmeier, M.Kaufmann: % ``Drawing High Degree Graphs with Low Bend Numbers'', % Technical Report, WSI-95-21.

% % H.Lauer and M.Kaufmann, % ``Design and Implementation of the Extensible % Graph-Drawing System Dr.Graph,'' % Technical Report, WSI-96-05.

% % U. Fößmeier and M. Kaufmann: % ``On Exact Solutions for the Rectilinear Steiner Problem, % Part I: Theoretical Results'' , % Technical Report, WSI-96-09, updated version.

% %

Michael Kaufmann
Last modified: Wed Mar 6 15:50:26 MET