Fabian Lipp, M. Sc.

• 
  The Stub Resolution of 1-Planar Graphs. Kaufmann, Michael; Kratochvil, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Valtr, Pavel. In WALCOM: Algorithms and Computation, Bd. 12049 von Lecture Notes in Computer Science, M. S. Rahman, K. Sadakane, W.-K. Sung (Hrsg.), S. 170–182. Springer, 2020.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  The resolution of a drawing plays a crucial role when defining criteria for its quality. In the past, grid resolution, edge-length resolution, angular resolution and crossing resolution have been investigated. In this paper, we investigate the stub resolution, a recently introduced criterion for nonplanar drawings. A crossed edge is divided into parts, called stubs, which should not be too short for the sake of readability. Thus, the stub resolution of a drawing is defined as the minimum ratio between the length of a stub and the length of the entire edge, over all the edges of the drawing. We consider 1-planar graphs and we explore scenarios in which near optimal stub resolution, i.e. arbitrarily close to {\\($}{\$\)}{\backslash}frac{\{}1{\}}{\{}2{\}}{\\($}{\$\)}, can be obtained in drawings with zero, one, or two bends per edge, as well as further resolution criteria, such as angular and crossing resolution. In particular, our main contributions are as follows: (i) Every 1-planar graph with independent crossing edges has a straight-line drawing with near optimal stub resolution; (ii) Every 1-planar graph has a 1-bend drawing with near optimal stub resolution.

  @inproceedings{10.1007/978-3-030-39881-1_15, abstract = {The resolution of a drawing plays a crucial role when defining criteria for its quality. In the past, grid resolution, edge-length resolution, angular resolution and crossing resolution have been investigated. In this paper, we investigate the stub resolution, a recently introduced criterion for nonplanar drawings. A crossed edge is divided into parts, called stubs, which should not be too short for the sake of readability. Thus, the stub resolution of a drawing is defined as the minimum ratio between the length of a stub and the length of the entire edge, over all the edges of the drawing. We consider 1-planar graphs and we explore scenarios in which near optimal stub resolution, i.e. arbitrarily close to {\$}{\$}{\backslash}frac{\{}1{\}}{\{}2{\}}{\$}{\$}, can be obtained in drawings with zero, one, or two bends per edge, as well as further resolution criteria, such as angular and crossing resolution. In particular, our main contributions are as follows: (i) Every 1-planar graph with independent crossing edges has a straight-line drawing with near optimal stub resolution; (ii) Every 1-planar graph has a 1-bend drawing with near optimal stub resolution.}, author = {Kaufmann, Michael and Kratochvil, Jan and Lipp, Fabian and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi and Valtr, Pavel}, booktitle = {WALCOM: Algorithms and Computation}, editor = {Rahman, M. Sohel and Sadakane, Kunihiko and Sung, Wing-Kin}, keywords = {stub}, pages = {170–182}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {The Stub Resolution of 1-Planar Graphs}, volume = 12049, year = 2020 }
• 
  Drawing Graphs on Few Lines and Few Planes. Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander. In Journal of Computational Geometry, 11(1), S. 433–475. 2020.
  • [ Abstract ]
  • [ BibTeX ]
  We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many relations to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. par We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. par We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). par We pay special attention to planar graphs. For example, we show that there are qplanar graphs that can be drawn in 3-space on asymptotically fewer lines than in the plane.

  @article{cflrvw-dgflf-JoCG20, abstract = {We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many relations to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. \par We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. \par We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). \par We pay special attention to planar graphs. For example, we show that there are qplanar graphs that can be drawn in 3-space on asymptotically fewer lines than in the plane.}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, journal = {Journal of Computational Geometry}, keywords = {myown}, number = 1, pages = {433–475}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 11, year = 2020 }
• 
  Machine Learning for Optical Network Security Monitoring: A Practical Perspective. Furdek, Marija; Natalino, Carlos; Lipp, Fabian; Hock, David; Di Giglio, Andrea; Schiano, Marco. In Journal of Lightwave Technology, 38(11), S. 2860–2871. IEEE, 2020.
  • [ BibTeX ]
  • [ URL ]
  @article{furdek2020machine, author = {Furdek, Marija and Natalino, Carlos and Lipp, Fabian and Hock, David and Di Giglio, Andrea and Schiano, Marco}, journal = {Journal of Lightwave Technology}, keywords = {myown}, number = 11, pages = {2860–2871}, publisher = {IEEE}, title = {Machine Learning for Optical Network Security Monitoring: A Practical Perspective}, volume = 38, year = 2020 }

• 
  NOracle: Who is communicating with whom in my network?. Kalmbach, Patrick; Hock, David; Lipp, Fabian; Kellerer, Wolfgang; Blenk, Andreas. In SIGCOMM Posters and Demos, S. 48–50. ACM, 2019.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{conf/sigcomm/KalmbachHLKB19, author = {Kalmbach, Patrick and Hock, David and Lipp, Fabian and Kellerer, Wolfgang and Blenk, Andreas}, booktitle = {SIGCOMM Posters and Demos}, crossref = {conf/sigcomm/2019p}, keywords = {myown}, pages = {48-50}, publisher = {ACM}, title = {NOracle: Who is communicating with whom in my network?}, year = 2019 }
• 
  Compact drawings of 1-planar graphs with right-angle crossings and few bends. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes. In Comput. Geom., 84, S. 50–68. 2019.
  • [ BibTeX ]
  • [ URL ]
  @article{journals/comgeo/ChaplickLWZ19, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, journal = {Comput. Geom.}, keywords = {myown}, pages = {50-68}, title = {Compact drawings of 1-planar graphs with right-angle crossings and few bends.}, volume = 84, year = 2019 }

• 
  Bounded Stub Resolution for Some Maximal 1-Planar Graphs. Kaufmann, Michael; Kratochvíl, Jan; Lipp, Fabian; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi N.; Valtr, Pavel. In CALDAM, Bd. 10743 von Lecture Notes in Computer Science, B. S. Panda, P. P. Goswami (Hrsg.), S. 214–220. Springer, 2018.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{conf/caldam/0001KLMRV18, author = {Kaufmann, Michael and Kratochvíl, Jan and Lipp, Fabian and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi N. and Valtr, Pavel}, booktitle = {CALDAM}, crossref = {conf/caldam/2018}, editor = {Panda, B. S. and Goswami, Partha P.}, keywords = {myown}, pages = {214-220}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Bounded Stub Resolution for Some Maximal 1-Planar Graphs.}, volume = 10743, year = 2018 }
• 
  Computing Storyline Visualizations with Few Block Crossings. van Dijk, Thomas C.; Lipp, Fabian; Markfelder, Peter; Wolff, Alexander. In Proc. 25th Int. Sympos. Graph Drawing Network Vis. (GD’17), Bd. 10692 von Lecture Notes in Computer Science, F. Frati, K.-L. Ma (Hrsg.), S. 365–378. Springer-Verlag, 2018.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{dlmw-csvfbc-GD2017, author = {van Dijk, Thomas C. and Lipp, Fabian and Markfelder, Peter and Wolff, Alexander}, booktitle = {Proc. 25th Int. Sympos. Graph Drawing Network Vis. (GD'17)}, editor = {Frati, Fabrizio and Ma, Kwan-Liu}, keywords = {myown}, pages = {365–378}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Computing Storyline Visualizations with Few Block Crossings}, volume = 10692, year = 2018 }
• 
  Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes. In Graph Drawing and Network Visualization - 26th International Symposium, {GD} 2018, Barcelona, Spain, September 26-28, 2018, Proceedings, Bd. 11282 von Lecture Notes in Computer Science, T. C. Biedl, A. Kerren (Hrsg.), S. 137–151. Springer, 2018.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every \($n$\)-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size \($O(n) O(n)$\). Then, we show that every \($n$\)-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size \($O(n^3) O(n^3)$\). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.

  @inproceedings{conf/gd/ChaplickLWZ18, abstract = {We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every $n$-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size $O(n) O(n)$. Then, we show that every $n$-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size $O(n^3) O(n^3)$. Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.}, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Graph Drawing and Network Visualization - 26th International Symposium, {GD} 2018, Barcelona, Spain, September 26-28, 2018, Proceedings}, editor = {Biedl, Therese C. and Kerren, Andreas}, keywords = {myown}, pages = {137–151}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends.}, volume = 11282, year = 2018 }
• 
  1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area. Chaplick, Steven; Lipp, Fabian; Wolff, Alexander; Zink, Johannes. In Proc. 34th Europ. Workshop Comput. Geom. (EuroCG’18), M. Korman, W. Mulzer (Hrsg.), S. 28:1–6. 2018.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{clwz-1brac-EuroCG18, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Proc. 34th Europ. Workshop Comput. Geom. (EuroCG'18)}, editor = {Korman, Matias and Mulzer, Wolfgang}, keywords = {myown}, pages = {28:1–6}, title = {1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area}, year = 2018 }

• 
  The Complexity of Drawing Graphs on Few Lines and Few Planes. Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander. In Proc. Algorithms Data Struct. Symp. (WADS’17), Bd. 10389, F. Ellen, A. Kolokolova, J.-R. Sack (Hrsg.), S. 265–276. Springer-Verlag, 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  It is well known that any graph admits a crossing-free straight-line drawing in  {\\($}{\$\)}{backslash}mathbb {\{}R{}} ^3{\\($}{\$\)} and that any planar graph admits the same even in  {\\($}{\$\)}{backslash}mathbb {\{}R{}} ^2{\\($}{\$\)} . For a graph G and {\\($}{\$\)}d {backslash}in {\backslash}{\{}2,3{\backslash}{\}}{\\($}{\$\)} , let {\\($}{\$\)}{backslash}rho ^1{\_}d(G){\\($}{\$\)} denote the minimum number of lines in {\\($}{\$\)}{backslash}mathbb {\{}R{}} ^d{\\($}{\$\)} that together can cover all edges of a drawing of G. For {\\($}{\$\)}d=2{\\($}{\$\)} , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.

  @inbook{cflrvw-cdgfl-WADS17, abstract = {It is well known that any graph admits a crossing-free straight-line drawing in  {\$}{\$}{\backslash}mathbb {\{}R{\}} ^3{\$}{\$} and that any planar graph admits the same even in  {\$}{\$}{\backslash}mathbb {\{}R{\}} ^2{\$}{\$} . For a graph G and {\$}{\$}d {\backslash}in {\backslash}{\{}2,3{\backslash}{\}}{\$}{\$} , let {\$}{\$}{\backslash}rho ^1{\_}d(G){\$}{\$} denote the minimum number of lines in {\$}{\$}{\backslash}mathbb {\{}R{\}} ^d{\$}{\$} that together can cover all edges of a drawing of G. For {\$}{\$}d=2{\$}{\$} , G must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results.}, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Proc. Algorithms Data Struct. Symp. (WADS'17)}, editor = {Ellen, Faith and Kolokolova, Antonina and Sack, Jörg-Rüdiger}, keywords = {number"}, pages = {265–276}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {The Complexity of Drawing Graphs on Few Lines and Few Planes}, volume = 10389, year = 2017 }
• 
  Block Crossings in Storyline Visualizations. van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander. In Journal of Graph Algorithms & Applications, 21(5), Y. Hu; M. Nöllenburg (Hrsg.), S. 873–913. 2017.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.

  @article{dfflmrsw-bcisv-JGAA17, abstract = {Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.}, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander}, editor = {Hu, Yifan and Nöllenburg, Martin}, journal = {Journal of Graph Algorithms \& Applications}, keywords = {storylines}, number = 5, pages = {873–913}, title = {Block Crossings in Storyline Visualizations}, volume = 21, year = 2017 }

• 
  Obstructing Visibilities with One Obstacle. Chaplick, Steven; Lipp, Fabian; Park, Ji{-}Won; Wolff, Alexander. In Proceedings of the 24th Int. Symp. on Graph Drawing & Network Visualization, Bd. 9801, Y. Hu, M. Nöllenburg (Hrsg.), S. 295–308. Springer, 2016.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{clpw-obwoo-GD16, author = {Chaplick, Steven and Lipp, Fabian and Park, Ji{-}Won and Wolff, Alexander}, booktitle = {Proceedings of the 24th Int. Symp. on Graph Drawing & Network Visualization}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, pages = {295-308}, publisher = {Springer}, title = {Obstructing Visibilities with One Obstacle}, volume = 9801, year = 2016 }
• 
  Block Crossings in Storyline Visualizations. van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander. In Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD’16), Bd. 9801 von Lecture Notes in Computer Science, Y. Hu, M. Nöllenburg (Hrsg.), S. 382–398. Springer-Verlag, 2016.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{DBLP:journals/corr/Dijk0FLMRSW16, author = {van Dijk, Thomas C. and Fink, Martin and Fischer, Norbert and Lipp, Fabian and Markfelder, Peter and Ravsky, Alexander and Suri, Subhash and Wolff, Alexander}, booktitle = {Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD'16)}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, note = {Best paper award.}, pages = {382-398}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Block Crossings in Storyline Visualizations}, volume = 9801, year = 2016 }
• 
  Drawing Graphs on Few Lines and Few Planes. Chaplick, Steven; Fleszar, Krzysztof; Lipp, Fabian; Ravsky, Alexander; Verbitsky, Oleg; Wolff, Alexander. In Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD’16), Bd. 9801, Y. Hu, M. Nöllenburg (Hrsg.), S. 166–180. Springer, 2016.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{cflrvw-dgoflafp-GD16, author = {Chaplick, Steven and Fleszar, Krzysztof and Lipp, Fabian and Ravsky, Alexander and Verbitsky, Oleg and Wolff, Alexander}, booktitle = {Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD'16)}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, pages = {166-180}, publisher = {Springer}, title = {Drawing Graphs on Few Lines and Few Planes}, volume = 9801, year = 2016 }
• 
  Simultaneous Orthogonal Planarity. Angelini, Patrizio; Chaplick, Steven; Cornelsen, Sabine; Lozzo, Giordano Da; Battista, Giuseppe Di; Eades, Peter; Kindermann, Philipp; Kratochv{í}l, Jan; Lipp, Fabian; Rutter, Ignaz. In Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD’16), Bd. 9801, Y. Hu, M. Nöllenburg (Hrsg.), S. 532–545. Springer, 2016.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{acclbekklr-sop-GD16, author = {Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Lozzo, Giordano Da and Battista, Giuseppe Di and Eades, Peter and Kindermann, Philipp and Kratochv{\'i}l, Jan and Lipp, Fabian and Rutter, Ignaz}, booktitle = {Proc. 24th Int. Sympos. Graph Drawing Network Vis. (GD'16)}, editor = {Hu, Yifan and Nöllenburg, Martin}, keywords = {myown}, pages = {532-545}, publisher = {Springer}, title = {Simultaneous Orthogonal Planarity}, volume = 9801, year = 2016 }
• 
  Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Lipp, Fabian; Wolff, Alexander; Zink, Johannes. In Algorithms, 9(3), S. 53. 2016.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only O ( m + n log n ) time per iteration when laying out a graph with n vertices and m edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).

  @article{lwz-ffdgd-algorithms16, abstract = {The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs, as they compute a quadratic number of forces in each iteration. We give a new algorithm that takes only O ( m + n log n ) time per iteration when laying out a graph with n vertices and m edges. Our algorithm approximates the true forces using the so-called well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime, even on graphs with less than a hundred vertices, without a significant influence on the quality of the drawings (in terms of the number of crossings and deviation in edge lengths).}, author = {Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, journal = {Algorithms}, keywords = {well-separated-pair-decomposition}, number = 3, pages = 53, title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition}, volume = 9, year = 2016 }

• 
  Solving Optimization Problems on Orthogonal Ray Graphs. Chaplick, Steven; Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander. In Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCG\($^2$\)’15), S. 2 pp. 2015.
  • [ BibTeX ]
  @inproceedings{cklw-sopor-JCDCGG15, author = {Chaplick, Steven and Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proc. Japan. Conf. Discrete Comput. Geom. Graphs (JCDCG$^2$'15)}, keywords = {myown}, note = {Abstract}, pages = {2 pp.}, title = {Solving Optimization Problems on Orthogonal Ray Graphs}, year = 2015 }
• 
  Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition. Lipp, Fabian; Wolff, Alexander; Zink, Johannes. In Graph Drawing and Network Visualization, Bd. 9411, E. Di Giacomo, A. Lubiw (Hrsg.), S. 52–59. Springer International Publishing, 2015.
  • [ BibTeX ]
  • [ URL ]
  @incollection{noKey, author = {Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, booktitle = {Graph Drawing and Network Visualization}, editor = {Di Giacomo, Emilio and Lubiw, Anna}, keywords = {force-directed}, pages = {52-59}, publisher = {Springer International Publishing}, series = {Lecture Notes in Computer Science}, title = {Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition}, volume = 9411, year = 2015 }

• 
  Boundary Labeling for Annotations in Texts. Lipp, Fabian. 2014.
  • [ BibTeX ]
  • [ URL ]
  @mastersthesis{lipp2014boundary, author = {Lipp, Fabian}, keywords = {labeling}, title = {Boundary Labeling for Annotations in Texts}, type = {master thesis}, year = 2014 }
• 
  Luatodonotes: Boundary Labeling for Annotations in Texts. Kindermann, Philipp; Lipp, Fabian; Wolff, Alexander. In Proc. 22nd Int. Sympos. Graph Drawing (GD’14), Bd. 8871 von Lecture Notes in Computer Science, C. Duncan, A. Symvonis (Hrsg.), S. 76–88. Springer-Verlag, 2014.
  • [ BibTeX ]
  • [ URL ]
  @inproceedings{klw-lblat-GD14, author = {Kindermann, Philipp and Lipp, Fabian and Wolff, Alexander}, booktitle = {Proc. 22nd Int. Sympos. Graph Drawing (GD'14)}, editor = {Duncan, Christian and Symvonis, Antonios}, keywords = {annotations}, pages = {76-88}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, title = {Luatodonotes: Boundary Labeling for Annotations in Texts}, volume = 8871, year = 2014 }

• 
  Computing the Flip Distance of Triangulations. Lipp, Fabian. 2012.
  • [ BibTeX ]
  • [ URL ]
  @mastersthesis{lipp2012computing, author = {Lipp, Fabian}, keywords = {flip}, title = {Computing the Flip Distance of Triangulations}, type = {bachelor thesis}, year = 2012 }
• 
  Structural Complexity of Multiobjective NP Search Problems. Fleszar, Krzysztof; Glaßer, Christian; Lipp, Fabian; Reitwießner, Christian; Witek, Maximilian. In LATIN 2012: Theoretical Informatics, Bd. 7256, D. Fernández-Baca (Hrsg.), S. 338–349. Springer Berlin Heidelberg, 2012.
  • [ Abstract ]
  • [ BibTeX ]
  • [ URL ]
  An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions. There are at least two computational tasks associated with an NP search problem: (i) Find out whether a solution exists. (ii) Compute an arbitrary solution. Further computational tasks arise in settings with multiple objectives, for example: (iii) Compute a solution that is minimal w.r.t. the first objective, while the second objective does not exceed some budget. Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P. For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.

  @incollection{noKey, abstract = {An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions. There are at least two computational tasks associated with an NP search problem: (i) Find out whether a solution exists. (ii) Compute an arbitrary solution. Further computational tasks arise in settings with multiple objectives, for example: (iii) Compute a solution that is minimal w.r.t. the first objective, while the second objective does not exceed some budget. Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P. For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.}, author = {Fleszar, Krzysztof and Glaßer, Christian and Lipp, Fabian and Reitwießner, Christian and Witek, Maximilian}, booktitle = {LATIN 2012: Theoretical Informatics}, editor = {Fernández-Baca, David}, keywords = {search}, pages = {338-349}, publisher = {Springer Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, title = {Structural Complexity of Multiobjective NP Search Problems}, volume = 7256, year = 2012 }