-
Notifications
You must be signed in to change notification settings - Fork 1
/
mainShort.tex
152 lines (119 loc) · 6.15 KB
/
mainShort.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
\documentclass[a4paper, 11pt]{llncs}
\usepackage[top=0.85in, bottom=0.85in, left=0.85in, right=0.85in]{geometry}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Packages
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{wrapfig}
\usepackage{enumerate}
\usepackage{cite}
\usepackage{pat}
\usepackage{paralist}
\usepackage{hyperref}
\usepackage{algorithm}
\usepackage{subfig}
%\usepackage{subfigure}
\usepackage{array}
\usepackage[noend]{algpseudocode}
\usepackage[usenames]{xcolor}
\usepackage{stmaryrd} % for lightning-symbol
\usepackage{mathtools} % for mathclap in \conf-definition
\usepackage{todonotes}
%\usepackage{compress}
\usepackage{times}
\usepackage{lineno}
%%\usepackage[font=small,labelfont=bf]{caption}
%\linespread{0.9}
\setlength{\floatsep}{0.9\floatsep}
\setlength{\belowcaptionskip}{2pt}
\setlength{\abovecaptionskip}{4pt}
\setlength{\textfloatsep}{5pt}
\setlength{\intextsep}{5pt}
\let\llncssubparagraph\subparagraph
\let\subparagraph\paragraph
\usepackage{titlesec}
\titlespacing*\section{0pt}{9pt plus 4pt minus 2pt}{3pt plus 2pt minus 0pt}
\titlespacing*\subsection{0pt}{9pt plus 4pt minus 2pt}{3pt plus 2pt minus 0pt}
\titlespacing*\subsubsection{0pt}{9pt plus 4pt minus 2pt}{3pt plus 2pt minus 0pt}
% Save the class definition of \subparagraph
% \let\llncssubparagraph\subparagraph
% Provide a definition to \subparagraph to keep titlesec happy
% \let\subparagraph\paragraph
% Load titlesec
% \usepackage[compact]{titlesec}
% \titlespacing\section{0pt}{6pt plus 4pt minus 2pt}{0pt plus 2pt minus 2pt}
% \titlespacing\subsection{0pt}{6pt plus 4pt minus 2pt}{0pt plus 2pt minus 2pt}
% \titlespacing\subsubsection{0pt}{6pt plus 4pt minus 2pt}{0pt plus 2pt minus 2pt}
\newtheorem{claimx}{Claim}{\bfseries}{\itshape}
%\spnewtheorem{lem}[obs]{Lemma}{\bfseries}{\itshape}
%\spnewtheorem{cor}[theorem]{Corollary}{\bfseries}{\itshape}
%\spnewtheorem{conj}[theorem]{Conjecture}{\bfseries}{\itshape}
%\spnewtheorem{prop}{Property}{\bfseries}{\itshape} % to make property stand out, like lemmata
\newcommand{\false}{\texttt{false}}
\newcommand{\true}{\texttt{true}}
\newcommand{\remove}[1]{}
\newcommand{\red}[1]{\textcolor{red}{#1}}
%% FROM PAT FILE
\newcommand{\reals}{\mathbb{R}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\dist}{{d}}
\newcommand{\Fary}{F\'ary}
\renewenvironment{proof}
{{\em Proof.\ }}{\hspace*{\fill}$\Box$\par\Vspace{2mm}}
\newenvironment{proofsketch}
{{\em Proof sketch.\ }}{\hspace*{\fill}$\Box$\par\Vspace{2mm}}
\begin{document}
\title{Every Collinear Set Is Free}
\author{Vida Dujmovi\'c\inst{1}\and Fabrizio Frati \inst{2} \and Daniel Gon\c{c}alves \inst{3} \and Pat Morin \inst{4} \and G\"unter Rote\inst{5}}
\institute{
University of Ottawa, Canada \hspace{5mm} \email{vida.dujmovic@uottawa.ca} \and
Roma Tre University, Italy \hspace{5mm} \email{frati@dia.uniroma3.it} \and
LIRMM (CNRS \& Universit\'{e} de Montpellier), France \hspace{5mm} \email{daniel.goncalves@lirmm.fr} \and
Carleton University, Canada \hspace{5mm} \email{morin@scs.carleton.ca}\and
Freie Universit\"at Berlin, Germany \hspace{5mm} \email{rote@inf.fu-berlin.de}}
\maketitle
\linenumbers
\begin{abstract}
We show that if a planar graph $G$ has a plane straight-line embedding
in which a subset $S$ of its vertices are collinear, then for any
set of points, $X$, in the plane with $|X|=|S|$ points, there is a plane straight-line
embedding of $G$ in which the vertices in $S$ are mapped to the points
in $X$. This solves an open problem posed by Ravsky and Verbitsky in
2008. In their terminology, we show that every collinear set is free.
This result has applications in graph drawing, including untangling,
column planarity, universal point subsets, and partial simultaneous
embeddings.
\end{abstract}
\newpage
\pagenumbering{arabic}
\pagestyle{plain}
\input{introductionShort.tex}
\input{definitionsShort.tex}
\input{agraphsShort.tex}
\input{triangulationsShort.tex}
\section{Concluding Problems}
In this paper we proved that every collinear set is a free set. Several problems concerning collinear and free sets remain open. Here we mention our favorite two.
Let $f(n)$ be the minimum, over all $n$-vertex planar graphs $G$, of the size of the largest collinear set in $G$. What is the growth rate of $f(n)$? The best known bounds are $f(n)\in\Omega(\sqrt{n})$ and $f(n)\in \mathcal{O}(n^\sigma)$, for $\sigma < 0.986$ \cite{bose.dujmovic.ea:polynomial,ravsky.verbitsky:on}. Our results prove that $f(n)$ is also the minimum size of the largest free set over all $n$-vertex planar graphs; this makes determining the growth rate of $f(n)$ even more relevant.
%
%\begin{op}
% What is the growth rate of $f(n)$?
%\end{op}
We find interesting to understand whether our main theorem can be generalized so that the $y$-coordinates are arbitrarily prescribed not only for the vertices on $Y$, but also for the crossing points of the edges with $Y$. Note that \thmref{main} {\em almost} gives this generalization, as every edge crossing $Y$ is at most $\epsilon$ away from its prescribed crossing point, for any arbitrarily small $\epsilon$.
%\section*{Acknowledgement}
%
%Part of this research was conducted during the 5\textsuperscript{th} and the 6\textsuperscript{th} Workshops on Geometry and Graphs, held at the Bellairs Research Institute, March 5--10, 2017 and March 11--16, 2018. We are grateful to the organizers and participants for providing a stimulating research environment.
%
%This work was initiated at the \emph{Fifth Workshop on Geometry and
% Graphs}, held at the Bellairs Research Institute, March 5--10, 2017 and
%was picked up again at the \emph{Sixth Workshop on Geometry and Graphs},
%March 11--16, 2018. We are grateful to the organizers and the other
%workshop participants for providing a stimulating research environment.
\newpage
\bibliographystyle{plain}
\bibliography{freecoll}
\end{document}