Drawing Graphs within Restricted Area

Aulbach, Maximilian and Fink, Martin and Schuhmann, Julian and Wolff, Alexander (2014) Drawing Graphs within Restricted Area. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 367-379 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_31).

Full text not available from this repository.


We study the problem of selecting a maximum-weight subgraph of a given graph such that the subgraph can be drawn within a prescribed drawing area subject to given non-uniform vertex sizes. We develop and analyze heuristics both for the general (undirected) case and for the use case of (directed) calculation graphs which are used to analyze the typical mistakes that high school students make when transforming mathematical expressions in the process of calculating, for example, sums of fractions.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_31
Classifications:G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.999 Others
M Methods > M.400 Force-directed / Energy-based
M Methods > M.500 Layered
P Styles > P.480 Layered
ID Code:1447

Repository Staff Only: item control page


Java Universal Network/Graph Framework (JUNG), http://www.jung.sourceforge.net

Aulbach, M., Fink, M., Schuhmann, J., Wolff, A.: Drawing graphs within restricted area. CoRR (2014), ArXiv e-print http://arxiv.org/abs/1409.0499

Bertault, F. (2000) A force-directed algorithm that preserves edge crossing properties. Inf. Proc. Letters 74: pp. 7-13

Coffman, E.G., Graham, R.L. (1972) Optimal scheduling for two-processor systems. Acta Inform. 1: pp. 200-213

Lozzo, G., Battista, G., Ingrassia, F. (2012) Drawing graphs on a smartphone. J. Graph Algorithms Appl. 16: pp. 109-126

Duncan, C.A., Gutwenger, C., Nachmanson, L., Sander, G. Graph drawing contest report. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 575-579

Dwyer, T., Marriott, K., Schreiber, F., Stuckey, P., Woodward, M., Wybrow, M. (2008) Exploration of networks using overview+detail with constraint-based cooperative layout. IEEE Trans. Vis. Comput. Graph. 14: pp. 1293-1300

Dwyer, T., Koren, Y., Marriott, K. (2006) IPSep-CoLa: An incremental procedure for separation constraint layout of graphs. IEEE Trans. Vis. Comput. Graph. 12: pp. 821-828

Dwyer, T., Marriott, K., Wybrow, M. Topology preserving constrained graph layout. In: Tollis, I.G., Patrignani, M. eds. (2009) Graph Drawing. Springer, Heidelberg, pp. 230-241

Fruchterman, T.M.J., Reingold, E.M. (1991) Graph drawing by force-directed placement. Softw. Pract. Exper. 21: pp. 1129-1164

Graham, R.L. (1966) Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45: pp. 1563-1581

He, W., Marriott, K. (1998) Constrained graph layout. Constraints 3: pp. 289-314

Hennecke, M. (2007) Rechengraphen. Math. Didact. 30: pp. 68-96

Patrignani, M. (2001) On the complexity of orthogonal compaction. Comput. Geom. Theory Appl. 19: pp. 47-67

Sander, G. A fast heuristic for hierarchical Manhattan layout. In: Brandenburg, F.J. eds. (1996) Graph Drawing. Springer, Heidelberg, pp. 447-458

Simonetto, P., Archambault, D., Auber, D., Bourqui, R. (2011) ImPrEd: An improved force-directed algorithm that prevents nodes from crossing edges. Comput. Graphics Forum 30: pp. 1071-1080

Sugiyama, K., Tagawa, S., Toda, M. (1981) Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cyber. 11: pp. 109-125