references.bib

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% --------------------------------------------------------------
%% Bibliography of i11
%%
%% --------------------------------------------------------------
%% Sections:
%% * STRING DEFINITIONS
%%   - general
%%   - authors
%%   - publishers
%%   - journals
%%   - conference proceedings
%% * MONOGRAPHS, PAPERS, THESES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% STRINGS DEFINITIONS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% --------------------------------------------------------------
%% general
%% --------------------------------------------------------------

@string{and = " and " }
@string{jan = "January" }
@string{feb = "February" }
@string{mar = "March" }
@string{apr = "April" }
@string{may = "May" }
@string{jun = "June" }
@string{jul = "July" }
@string{aug = "August" }
@string{sep = "September" }
@string{oct = "October" }
@string{nov = "November" }
@string{dec = "December" }
@string{first = "1st" }
@string{second = "2nd" }
@string{third = "3rd" }
@string{fourth = "4th" }
@string{fifth = "5th" }
@string{sixth = "6th" }
@string{seventh = "7th" }
@string{eighth = "8th" }
@string{ninth = "9th" }
@string{tenth = "10th" }


%% 
@InProceedings{RAHMAN06,
author="Rahman, Md. Saidur
and Egi, Noritsugu
and Nishizeki, Takao",
editor="Healy, Patrick
and Nikolov, Nikola S.",
title="No-bend Orthogonal Drawings of Series-Parallel Graphs",
booktitle="Graph Drawing",
year="2006",
publisher="Springer Berlin Heidelberg",
pages="409--420",
abstract="In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. Every series-parallel graph is planar. In this paper we give a linear-time algorithm to examine whether a series-parallel graph G of the maximum degree three has a no-bend orthogonal drawing and to find one if G has.",
isbn="978-3-540-31667-1"
}

@InProceedings{ZHOU05,
author="Zhou, Xiao
and Nishizeki, Takao",
editor="Deng, Xiaotie
and Du, Ding-Zhu",
title="Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends",
booktitle="Algorithms and Computation",
year="2005",
publisher="Springer Berlin Heidelberg",
pages="166--175",
abstract="In an orthogonal drawing of a planar graph G, each vertex is drawn as a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. A bend is a point where an edge changes its direction. A drawing of G is called an optimal orthogonal drawing if the number of bends is minimum among all orthogonal drawings of G. In this paper we give an algorithm to find an optimal orthogonal drawing of any given series-parallel graph of the maximum degree at most three. Our algorithm takes linear time, while the previously known best algorithm takes cubic time. Furthermore, our algorithm is much simpler than the previous one. We also obtain a best possible upper bound on the number of bends in an optimal drawing.",
isbn="978-3-540-32426-3"
}

@misc{BARTH17,
      title={A Topology-Shape-Metrics Framework for Ortho-Radial Graph Drawing}, 
      author={Lukas Barth and Benjamin Niedermann and Ignaz Rutter and Matthias Wolf},
      year={2021},
      eprint={2106.05734},
      archivePrefix={arXiv},
      primaryClass={cs.CG}
}

@misc{DIDIMO22,
  doi = {10.48550/ARXIV.2205.07500},
  
  url = {https://arxiv.org/abs/2205.07500},
  
  author = {Didimo, Walter and Kaufmann, Michael and Liotta, Giuseppe and Ortali, Giacomo},
  
  keywords = {Computational Geometry (cs.CG), Data Structures and Algorithms (cs.DS), FOS: Computer and information sciences, FOS: Computer and information sciences},
  
  title = {Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time},
  
  publisher = {arXiv},
  
  year = {2022},
  
  copyright = {arXiv.org perpetual, non-exclusive license}
}


@article{BATTISTA98,
author = {Di Battista, Giuseppe and Liotta, Giuseppe and Vargiu, Francesco},
title = {Spirality and Optimal Orthogonal Drawings},
journal = {SIAM Journal on Computing},
volume = {27},
number = {6},
pages = {1764-1811},
year = {1998},
doi = {10.1137/S0097539794262847},

URL = { 
    
        https://doi.org/10.1137/S0097%539794262847
    
    

},
eprint = { 
    
        https://doi.org/10.1137/S0097539794262847
    
    

}
,
    abstract = { We deal with the problem of constructing the orthogonal drawing of a graph with the minimum number of bends along the edges. The problem has been recently shown to be NP-complete in the general case. In this paper we introduce and study the new concept of spirality, which is a measure of how an orthogonal drawing is "rolled up," and develop a theory on the interplay between spirality and number of bends of orthogonal drawings. We exploit this theory to present polynomial time algorithms for two significant classes of graphs: series-parallel graphs and 3-planar graphs. Series-parallel graphs arise in a variety ofproblems such as scheduling, electrical networks, data-flow analysis, database logic programs, and circuit layout. Also, they play a central role in planarity problems. Furthermore, drawings of 3-planar graphs are a classical field of investigation. }
}

@INPROCEEDINGS{TAMMASSIA91,

  author={Tamassia, R. and Tollis, I.G. and Vitter, J.S.},

  booktitle={Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing}, 

  title={Lower bounds and parallel algorithms for planar orthogonal grid drawings}, 

  year={1991},

  volume={},

  number={},

  pages={386-393},

  doi={10.1109/SPDP.1991.218215}}

@InProceedings{GARG97,
author="Garg, Ashim
and Tamassia, Roberto",
editor="North, Stephen",
title="A new minimum cost flow algorithm with applications to graph drawing",
booktitle="Graph Drawing",
year="1997",
publisher="Springer Berlin Heidelberg",
pages="201--216",
abstract="Let N be a single-source single-sink flow network with n nodes, m arcs, and positive arc costs. We present a pseudo-polynomial algorithm that computes a maximum flow of minimum cost for N in time O($\chi$3/4m{\textsurd}log n), where~$\chi$ is the cost of the flow. This improves upon previously known methods for networks where the minimum cost of the flow is small. We also show an application of our flow algorithm to a well-known graph drawing problem. Namely, we show how to compute a planar orthogonal drawing with the minimum number of bends for an n- vertex embedded planar graph in time O(n7/4{\textsurd}log n). This is the first subquadratic algorithm for bend minimization. The previous best bound for this problem was O(n2 log n) [19].",
isbn="978-3-540-68048-2"
}



@Article{CORNELSEN12,
   author = {{Sabine} {Cornelsen} and {Andreas} {Karrenbauer}},
   title = {Accelerated Bend Minimization},
   journal = {Journal of Graph Algorithms and Applications},
   year = {2012},
   volume = {16},
   number = {3},
   pages = {635--650},
   doi = {10.7155/jgaa.00265}
} 

@article{GARG01,
author = {Garg, Ashim and Tamassia, Roberto},
title = {On the Computational Complexity of Upward and Rectilinear Planarity Testing},
journal = {SIAM Journal on Computing},
volume = {31},
number = {2},
pages = {601-625},
year = {2001},
doi = {10.1137/S0097539794277123},

URL = { 
    
        https://doi.org/10.1137/S0097539794277123
    
    

},
eprint = { 
    
        https://doi.org/10.1137/S0097539794277123
    
    

}
,
    abstract = { A directed graph is upward planar if it can be drawn in the plane such that every edge is a monotonically increasing curve in the vertical direction and no two edges cross. An undirected graph is rectilinear planar if it can be drawn in the plane such that every edge is a horizontal or vertical segment and no two edges cross. Testing upward planarity and rectilinear planarity are fundamental problems in the effective visualization of various graph and network structures. For example, upward planarity is useful for the display of order diagrams and subroutine-call graphs, while rectilinear planarity is useful for the display of circuit schematics and entity-relationship diagrams. We show that upward planarity testing and rectilinear planarity testing are NP-complete problems. We also show that it is NP-hard to approximate the minimum number of bends in a planar orthogonal drawing of an n-vertex graph with an \$O(n^{1-\epsilon})\$ error for any \$\epsilon > 0\$. }
}


@article{TAMASSIA87,
author = {Tamassia, Roberto},
title = {On Embedding a Graph in the Grid with the Minimum Number of Bends},
journal = {SIAM Journal on Computing},
volume = {16},
number = {3},
pages = {421-444},
year = {1987},
doi = {10.1137/0216030},

URL = { 
    
        https://doi.org/10.1137/0216030
    
    

},
eprint = { 
    
        https://doi.org/10.1137/0216030
    
    

}
}


@InProceedings{NIEDERMANN20,
author="Niedermann, Benjamin
and Rutter, Ignaz",
editor="Auber, David
and Valtr, Pavel",
title="An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings",
booktitle="Graph Drawing and Network Visualization",
year="2020",
publisher="Springer International Publishing",
pages="235--249",
abstract="An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation [1], we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by {\$}{\$}43.8 {\backslash}{\%}{\$}{\$}43.8{\%}on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.",
isbn="978-3-030-68766-3"
}

@InProceedings{BIEDL94,
author="Biedl, Therese
and Kant, Goos",
editor="van Leeuwen, Jan",
title="A better heuristic for orthogonal graph drawings",
booktitle="Algorithms --- ESA '94",
year="1994",
publisher="Springer Berlin Heidelberg",
pages="24--35",
abstract="An orthogonal drawing of a graph is an embedding in the plane such that all edges are drawn as sequences of horizontal and vertical segments. We present a linear time and space algorithm to draw any connected graph orthogonally on a grid of size n{\texttimes}n with at most 2n+2 bends. Each edge is bent at most twice.",
isbn="978-3-540-48794-4"
}

@InProceedings{BLAESIUS11,
author="Bl{\"a}sius, Thomas
and Krug, Marcus
and Rutter, Ignaz
and Wagner, Dorothea",
editor="Brandes, Ulrik
and Cornelsen, Sabine",
title="Orthogonal Graph Drawing with Flexibility Constraints",
booktitle="Graph Drawing",
year="2011",
publisher="Springer Berlin Heidelberg",
pages="92--104",
abstract="In this work we consider the following problem. Given a planar graph G with maximum degree 4 and a function flex: {\$}E {\backslash}longrightarrow {\{}{\backslash}mathbb{\{}N{\}}{\}}{\_}0{\$}that gives each edge a flexibility. Does G admit a planar embedding on the grid such that each edge e has at most flex(e) bends? Note that in our setting the combinatorial embedding of G is not fixed.",
isbn="978-3-642-18469-7"
}

@InProceedings{BLAESIUS15,
author="Bl{\"a}sius, Thomas
and Lehmann, Sebastian
and Rutter, Ignaz",
editor="Paschos, Vangelis Th.
and Widmayer, Peter",
title="Orthogonal Graph Drawing with Inflexible Edges",
booktitle="Algorithms and Complexity",
year="2015",
publisher="Springer International Publishing",
pages="61--73",
abstract="We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge {\$}{\$}e{\$}{\$}a natural number {\$}{\$}{\{}{\{}{\backslash}mathrm{\{}flex{\}}{\}}{\}}(e){\$}{\$}, its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge {\$}{\$}e{\$}{\$}has at most {\$}{\$}{\{}{\{}{\backslash}mathrm{\{}flex{\}}{\}}{\}}(e){\$}{\$}bends. It is known that FlexDraw is NP-hard if {\$}{\$}{\{}{\{}{\backslash}mathrm{\{}flex{\}}{\}}{\}}(e) = 0{\$}{\$}for every edge {\$}{\$}e{\$}{\$} [7]. On the other hand, FlexDraw can be solved efficiently if {\$}{\$}{\{}{\{}{\backslash}mathrm{\{}flex{\}}{\}}{\}}(e) {\backslash}ge 1{\$}{\$} [2] and is trivial if {\$}{\$}{\{}{\{}{\backslash}mathrm{\{}flex{\}}{\}}{\}}(e) {\backslash}ge 2{\$}{\$} [1] for every edge {\$}{\$}e{\$}{\$}.",
isbn="978-3-319-18173-8"
}

@InProceedings{BLAESIUS14,
author="Bl{\"a}sius, Thomas
and Br{\"u}ckner, Guido
and Rutter, Ignaz",
editor="Schulz, Andreas S.
and Wagner, Dorothea",
title="Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model",
booktitle="Algorithms - ESA 2014",
year="2014",
publisher="Springer Berlin Heidelberg",
pages="161--172",
abstract="We show that finding orthogonal grid embeddings of plane graphs (planar with fixed combinatorial embedding) with the minimum number of bends in the so-called Kandinsky model (allowing vertices of degree >{\thinspace}4) is NP-complete, thus solving a long-standing open problem. On the positive side, we give an efficient algorithm for several restricted variants, such as graphs of bounded branch width and a subexponential exact algorithm for general plane graphs.",
isbn="978-3-662-44777-2"
}

@article{HASHEMINEZHAD,
author = {Hasheminezhad, Mahdieh and Hashemi, S. Mehdi and Tahmasbi, Maryam},
year = {2009},
month = {06},
pages = {},
title = {Ortho-radial drawing of graphs},
volume = {44},
journal = {The Australasian Journal of Combinatorics [electronic only]}
}