1,721,221 research outputs found
Complexity Results for Three-dimensional Orthogonal Graph Drawing
No full textIn this paper we consider the problem of finding three-dimensional orthogonal drawings of maximum degree six graphs from the computational complexity perspective. We introduce a 3SAT reduction framework that can be used to prove the NP-hardness of finding three-dimensional orthogonal drawings with specific constraints. By using the framework we show that, given a three-dimensional orthogonal shape of a graph (a description of the sequence of axis-parallel segments of each edge), finding the coordinates for nodes and bends such that the drawing has no intersection is NP-complete. Conversely, we show that if node coordinates are fixed, finding a shape for the edges that is compatible with a non-intersecting drawing is a feasible problem, which becomes NP-complete if a maximum of two bends per edge is allowed. We comment on the impact of these results on the two open problems of determining whether a graph always admits a drawing with at most two bends per edge and of characterizing orthogonal shapes admitting an orthogonal drawing without intersections.
On the Complexity of Orthogonal Compaction
No full textAbstractWe consider three closely related optimization problems, arising from the graph drawing and the VLSI research areas, and conjectured to be NP-hard, and we prove that, in fact, they are NP-complete. Starting from an orthogonal representation of a graph, i.e., a description of the shape of the edges that does not specify segment lengths or vertex positions, the three problems consist of providing an orthogonal grid drawing of it, while minimizing the area, the total edge length, or the maximum edge length, respectively.This result confirms a long surviving conjecture of NP-hardness, justifies the research about applying sophisticated, yet possibly time consuming, techniques to obtain optimally compacted orthogonal grid drawings, and discourages the quest for an optimally compacting polynomial-time algorithm
A Note on the Self-similarity of Some Orthogonal Drawings
No full textLarge graphs are difficult to browse and to visually explore. This note adds up evidence that some graph drawing techniques, which produce readable layouts when applied to medium-size graphs, yield self-similar patterns when launched on huge graphs. To prove this, we consider the problem of assessing the self-similarity of graph drawings, and measure the box-counting dimension of the output of three algorithms, each using a different approach for producing orthogonal grid drawings with a reduced number of bends.
Work partially supported by European Commission – Fet Open project COSIN – COevolution and Self-organisation In dynamical Networks – IST-2001-33555, by European Commission – Fet Open project DELIS – Dynamically Evolving Large Scale Information Systems – Contract no 001907, by ldquoProgetto ALINWEB: Algoritmica per Internet e per il Webrdquo, MIUR Programmi di Ricerca Scientifica di Rilevante Interesse Nazionale, and by ldquoThe Multichannel Adaptive Information Systems (MAIS) Projectrdquo, MIUR Fondo per gli Investimenti della Ricerca di Base
Dynamic Analysis of the Autonomous System Graph
No full textIn this paper we investigate to what extent the information
provided by BGP routing tables about the graph
of the Autonomous Systems (ASes) can be used to understand
dynamic phenomena occurring in the network. First,
we classify the time scales at which such an analysis can
be performed and, consequently, the kinds of phenomena
that could be anticipated. Second, we improve cutting-edge
technologies used to analyze the structure of the network,
most notably spectral methods for graph clustering, in order
to be able to analyze a whole sequence of consecutive
snapshots that capture the temporal evolution of the
network. Finally, we use such tools to analyze the data
collected by the Oregon RouteViews project [20] during
the last few years. We confirm stable properties of the AS
graph, find major trends and notice that events occurring
on a smaller time-frame, like worm-attacks, misconfigurations,
outages, DDoS attacks, etc. seem to have a very diverse
degree of impact on the AS graph structure, which
suggests that these techniques could be used to distinguish
some of them.
Graph Drawing, 16th International Symposium, GD '08, Heraklion, Crete, Greece, September 2008, Revised Papers
No full textLecture Notes in Computer Science
Special issue with selected papers from the 20th international symposium on graph drawing, GD 2012: Guest editors' foreword.
No full text
- …
