DROPS

Document

08191 Working Group Report – Edge Thresholding

Authors: Patrick Healy and Tim Dwyer

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract

When working with very large networks it is typical for scientists to present a ``thinned out'' version of the network in order to avoid the clutter of the entire network. For example in the hypothetical case of illustrating trading patterns between groups of nations it might be appropriate to limit the inclusion of inter-nation edges to all those that are significant in terms of their weight but do not, say, associate with a country outside the grouping. Arising from a discussion during one of the introductory sessions we became interested in a problem relating to the discovery of ``key events'' in a network, in terms of an ordered addition of edges to the network.

Cite as

Patrick Healy and Tim Dwyer. 08191 Working Group Report – Edge Thresholding. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{healy_et_al:DagSemProc.08191.3,
  author =	{Healy, Patrick and Dwyer, Tim},
  title =	{{08191 Working Group Report – Edge Thresholding}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.3},
  URN =		{urn:nbn:de:0030-drops-15570},
  doi =		{10.4230/DagSemProc.08191.3},
  annote =	{Keywords: Graph drawing, edge thresholding}
}

Document

DOI: 10.4230/DagSemProc.05191.6

On Layering Directed Acyclic Graphs

Authors: Martin Harrigan and Patrick Healy

Published in: Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)

Abstract

We consider the problem of layering a directed acyclic graph with minimum dummy nodes. We present a new Integer Linear Programming (ILP) formulation of the problem based on a set of fundamental cycles in the underlying undirected graph and show that it can be solved in polynomial time. We outline some of the advantages of the formulation. Each solution defines a family of layerings with the same number of dummy nodes. We can also transform one solution into another by adding or removing certain combinations of dummy nodes, thus allowing the consideration of other aesthetics.

Cite as

Martin Harrigan and Patrick Healy. On Layering Directed Acyclic Graphs. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{harrigan_et_al:DagSemProc.05191.6,
  author =	{Harrigan, Martin and Healy, Patrick},
  title =	{{On Layering Directed Acyclic Graphs}},
  booktitle =	{Graph Drawing},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5191},
  editor =	{Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.6},
  URN =		{urn:nbn:de:0030-drops-3430},
  doi =		{10.4230/DagSemProc.05191.6},
  annote =	{Keywords: Graph Drawing, Hierarchical Drawings, Layerings, Minimum Dummy Nodes}
}

Search Results

Documents authored by Healy, Patrick

08191 Working Group Report – Edge Thresholding

Abstract

Cite as

On Layering Directed Acyclic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message