Article

Orthogonal hypergraph routing for improved visibility

Authors:

Thomas Eschbach,

Wolfgang Günther,

Bernd BeckerAuthors Info & Claims

GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI

Pages 385 - 388

https://doi.org/10.1145/988952.989045

Published: 26 April 2004 Publication History

Get Access

References

[1]

F. Brglez, D. Bryan, and K. Kozminski. Combinational profiles of sequential benchmark circuits. Int'l Symp. Circ. and Systems, pages 1929--1934, 1989.

Google Scholar

[2]

P. Eades and D. Kelly. Heuristics for reducing crossings in 2-layered networks. Ars Combin., 21(A):89--98, 1986.

Google Scholar

[3]

P. Eades and N. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379--403, 1994.

Digital Library

Google Scholar

[4]

T. Eschbach, W. Günther, and B. Becker. Crossing reduction for orthogonal circuit visualization. Proceedings of the 2003 International Conference on VLSI, Las Vegas, USA, CSREA Press, pages 107--113, 2003.

Digital Library

Google Scholar

[5]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. Freeman, 1979.

Digital Library

Google Scholar

[6]

M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4:312--316, 1983.

Crossref

Google Scholar

[7]

R. Karp. Reducibility among combinatorial problems, in Complexity of Computer Computations (R.E. Miller and J.M. Thatcher, eds.). Plenum Press, 1972.

Google Scholar

[8]

T. Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. Teubner, Wiley, 1990.

Digital Library

Google Scholar

[9]

E. Mäkinen. How to draw a hypergraph. International Journal of Computer and Mathematics, 34:177--185, 1990.

Crossref

Google Scholar

[10]

K. McElvain. Benchmark set: Version 4.0. International Workshop on Logic Synthesis, 1993.

Google Scholar

[11]

P. Mutzel, C. Gutwenger, R. Brockenauer, S. Fialko, G. W. Klau, M. Krüger, T. Ziegler, S. Näher, D. Alberts, D. Ambras, G. Koch, M. Jünger, C. Buchheim, and S. Leipert. AGD: A library of algorithms for graph drawing. Proceedings of the 6th International Symposium on Graph Drawing, LNCS 1547:456--457, 1998.

Digital Library

Google Scholar

[12]

R. Rudell. Dynamic variable ordering for ordered binary decision diagrams. ICCAD, pages 42--47, 1993.

Digital Library

Google Scholar

[13]

G. Sander. Layout of directed hypergraphs with orthogonal hyperedges. 11th Int'l Symposium on Graph Drawing 2003, LNCS 2912:381--386, 2004.

Google Scholar

[14]

N. Sherwani. Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers, Norwell, Massachusetts, second edition, 1995.

Digital Library

Google Scholar

[15]

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transaction on Systems, Man and Cybernetics, 11(2):109--125, 1981.

Crossref

Google Scholar

Cited By

View all

Di Bartolomeo SPister ABuono PPlaisant CDunne CFekete J(2022)Six methods for transforming layered hypergraphs to apply layered graph layout algorithmsComputer Graphics Forum10.1111/cgf.1453841:3(259-270)Online publication date: 12-Aug-2022
https://doi.org/10.1111/cgf.14538
Helmke SGoetze BScheffler RWrobel G(2021)Interactive, Orthogonal Hyperedge Routing in Schematic Diagrams Assisted by Layout AutomatismsDiagrammatic Representation and Inference10.1007/978-3-030-86062-2_2(20-27)Online publication date: 21-Sep-2021
https://doi.org/10.1007/978-3-030-86062-2_2
Eschbach TGunther WBecker B(2005)Orthogonal Circuit Visualization Improved by Merging the Placement and Routing PhasesProceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design10.1109/ICVD.2005.134(433-438)Online publication date: 3-Jan-2005
https://dl.acm.org/doi/10.1109/ICVD.2005.134

Orthogonal hypergraph routing for improved visibility
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation

Recommendations

Hypergraph Based Berge Hypergraphs
Abstract
Fix a hypergraph $F$ . A hypergraph $H$ is called a Berge copy of $F$ or Berge- $F$ if we can choose a subset of each hyperedge of $H$ to obtain a copy of $F$ . A hypergraph $H$ is Berge- $F$ -free if it does not contain a subhypergraph which is Berge copy of $F$ . This ... $^{}$
An improved AODV routing protocol for MANETs
WiCOM'09: Proceedings of the 5th International Conference on Wireless communications, networking and mobile computing

A hybrid routing protocol for mobile ad hoc networks (MANETs) called improved ad hoc on-demand distance vector (IAODV) is proposed in this paper. It merges the AODV routing protocol with multipath and path accumulation (PA). The performance of IAODV is ...
A hypergraph extension of Turán's theorem

Fix l≥r≥2. Let H_l+1^(r) be the r-uniform hypergraph obtained from the complete graph K_l+1 by enlarging each edge with a set of r - 2 new vertices. Thus H_l+1^(r) has (r - 2) (l+1 2) + l + 1 vertices and (l+1 2) edges. We prove that the maximum number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI

April 2004

479 pages

ISBN:1581138539

DOI:10.1145/988952

General Chair:
David Garrett
Bell Labs Research, Lucent Technologies
,
Program Chairs:
John Lach
University of Virginia
,
Charles Zukowski
Columbia University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 April 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

GLSVLSI04

Sponsor:

GLSVLSI04: Great Lakes Symposium on VLSI 2004

April 26 - 28, 2004

MA, Boston, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25

Sponsor:
sigda

Great Lakes Symposium on VLSI 2025

June 30 - July 2, 2025

New Orleans , LA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
222
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)2

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Di Bartolomeo SPister ABuono PPlaisant CDunne CFekete J(2022)Six methods for transforming layered hypergraphs to apply layered graph layout algorithmsComputer Graphics Forum10.1111/cgf.1453841:3(259-270)Online publication date: 12-Aug-2022
https://doi.org/10.1111/cgf.14538
Helmke SGoetze BScheffler RWrobel G(2021)Interactive, Orthogonal Hyperedge Routing in Schematic Diagrams Assisted by Layout AutomatismsDiagrammatic Representation and Inference10.1007/978-3-030-86062-2_2(20-27)Online publication date: 21-Sep-2021
https://doi.org/10.1007/978-3-030-86062-2_2
Eschbach TGunther WBecker B(2005)Orthogonal Circuit Visualization Improved by Merging the Placement and Routing PhasesProceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design10.1109/ICVD.2005.134(433-438)Online publication date: 3-Jan-2005
https://dl.acm.org/doi/10.1109/ICVD.2005.134

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Hypergraph Based Berge Hypergraphs

An improved AODV routing protocol for MANETs

A hypergraph extension of Turán's theorem