* Blom and Bakker, (2002) Blom, H. and Bakker, G. (2002).  Conflict probability and incrossing probability in air traffic management.  Proc. 41st IEEE Conference on Decision and Control, Las Vegas, NV.
  * Burgain et al., (2009) Burgain, P., Pinon, O., Feron, E., Clarke, J.-P., and Mavris, D. (2009).  On the value of information within a collaborative decision making framework for airport departure operations.  Proc. IEEE/AIAA 28th Digital Avionics Systems Conference, Orlando, FL.
  * Cavusoglu and Macario, (2021) Cavusoglu, S. and Macario, R. (2021).  Minimum delay or maximum efficiency? Rising productivity of available capacity at airports: Review of current practice and future needs.  Journal of Air Transport Management, 90:101947.
  * Corolli et al., (2017) Corolli, L., Lulli, G., Ntaimo, L., and Venkatachalam, S. (2017).  A two-stage stochastic integer programming model for air traffic flow management.  IMA Journal of Management Mathematics, 28:19–40.
  * Cox and Miller, (1960) Cox, D. and Miller, H. (1960).  The Theory of Stochastic Processes.  Chapman & Hall.
  * de Neufville and Odoni, (2013) de Neufville, R. and Odoni, A. (2013).  Airport Systems: Planning, Design and Management, 2nd edition.  McGraw-Hill.
  * Dear, (1976) Dear, R. (1976).  The Dynamic Scheduling of Aircraft in the Near Terminal Area.  Technical report R76-9, MIT Flight Transportation Laboratory.
  * Estes and Ball, (2020) Estes, A. and Ball, M. (2020).  Equity and Strength in Stochastic Integer Programming Models for the Dynamic Single Airport Ground-Holding Problem.  Transportation Science, 54(4):944–955.
  * (17) Eurocontrol (2022a).  All-causes delays to air transport in europe annual 2021.  https://www.eurocontrol.int/publication/all-causes-delay-and-cancellations-air-transport-europe-2021.  Accessed on May 1, 2022.
  * (18) Eurocontrol (2022b).  Covid 19 Impact on European Aviation: 28 September 2022.  https://www.eurocontrol.int/sites/default/files/2022-09/eurocontrol-comprehensive-air-traffic-assessment-20220929.pdf.  Accessed on October 20, 2022.
  * Folks and Chhikara, (1978) Folks, J. and Chhikara, R. (1978).  The Inverse Gaussian Distribution and its Statistical Application - A Review.  Journal of the Royal Statistical Society: Series B (Methodological), 40(3):263–275.
  * Gilbo, (1993) Gilbo, E. (1993).  Airport capacity: Representation, estimation, optimization.  IEEE Transactions on Control Systems Technology, 1(3):144–154.
  * Gupta, (2010) Gupta, S. (2010).  Transient Analysis of $D(t)/M(t)/1$ Queuing System with Applications to Computing Airport Delays.  Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA.
  * Hansen et al., (2009) Hansen, M., Nikoleris, T., Lovell, D., Vlachou, K., and Odoni, A. (2009).  Use of Queueing Models to Estimate Delay Savings from 4D Trajectory Precision.  Proc. 8th USA/Europe Air Traffic Management R&D Seminar, Napa, CA.
  * Heidt et al., (2016) Heidt, A., Helmke, H., Kapolke, M., Liers, F., and Martin, A. (2016).  Robust runway scheduling under uncertain conditions.  Journal of Air Transport Management, 56:28–37.
  * Hu and Chen, (2005) Hu, X. and Chen, W. (2005).  Receding horizon control for aircraft arrival sequencing and scheduling.  IEEE Transactions on Intelligent Transportation Systems, 6:189–197.
  * Jacquillat and Odoni, (2015) Jacquillat, A. and Odoni, A. (2015).  An Integrated Scheduling and Operations Approach to Airport Congestion Mitigation.  Operations Research, 63(6):1390–1410.
  * Jacquillat and Odoni, (2018) Jacquillat, A. and Odoni, A. (2018).  A roadmap toward airport demand and capacity management.  Transportation Research Part A, 114:168–185.
  * Jacquillat et al., (2017) Jacquillat, A., Odoni, A., and Webster, M. (2017).  Dynamic Control of Runway Configurations and of Arrival and Service Departure Rates at JFK Airport Under Stochastic Queue Conditions.  Transportation Science, 51(1):155–176.
  * Juan et al., (2015) Juan, A., Faulin, J., Grasman, S., Rabe, M., and Figueira, G. (2015).  A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems.  Operations Research Perspectives, 2:62–72.
  * Khassiba et al., (2020) Khassiba, A., Bastin, F., Cafieri, S., Gendron, B., and Mongeau, M. (2020).  Two-Stage Stochastic Mixed-Integer Programming with Chance Constraints for Extended Aircraft Arrival Management.  Transportation Science, 54(4):897–919.
  * Kivestu, (1976) Kivestu, P. (1976).  Alternative methods of investigating the time-dependent $M/G/K$ queue.  Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA.
  * Koopman, (1972) Koopman, B. (1972).  Air-Terminal Queues under Time-Dependent Conditions.  Operations Research, 20(6):1089–1114.
  * Liu et al., (2018) Liu, M., Liang, B., Zheng, F., Chu, C., and Chu, F. (2018).  A Two-stage Stochastic Programming Approach for Aircraft Landing Problem.  Proc. 2018 International Conference on Service Systems and Service Management (ICSSSM), Hangzhou, China.
  * Liu et al., (2020) Liu, M., Liang, B., Zhu, M., and Chu, C. (2020).  Stochastic Runway Scheduling Problem With Partial Distribution Information of Random Parameters.  IEEE Access, 8:68460–68473.
  * Liu and Hwang, (2014) Liu, W. and Hwang, I. (2014).  Probabilistic Aircraft Midair Conflict Resolution Using Stochastic Optimal Control.  IEEE Transactions on Intelligent Transportation Systems, 15(1):37–46.
  * Malone, (1995) Malone, K. (1995).  Dynamic queuing systems: Behavior and approximations for individual queues and networks.  Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA.
  * Montlaur and Delgado, (2017) Montlaur, A. and Delgado, L. (2017).  Flight and passenger delay assignment optimization strategies.  Transportation Research Part C, 81:99–117.
  * Nelson, (2013) Nelson, B. (2013).  Foundations and methods of stochastic simulation: a first course.  Springer Science & Business Media.
  * Newell, (1979) Newell, G. (1979).  Airport Capacity and Delays.  Transportation Science, 13(3):201–241.
  * Odoni, (1987) Odoni, A. (1987).  The Flow Management Problem in Air Traffic Control.  In: Odoni, A.R. and Szego, G. (eds). Flow Control of Congested Networks. Springer-Verlag, Berlin, Germany.
  * Psaraftis, (1978) Psaraftis, H. (1978).  A Dynamic Programming Approach to the Aircraft Sequencing Problem.  Technical report R78-4, MIT Flight Transportation Laboratory.
  * Pyrgiotis and Odoni, (2016) Pyrgiotis, N. and Odoni, A. (2016).  On the Impact of Scheduling Limits: A Case Study at Newark Liberty International Airport.  Transportation Science, 50(1):150–165.
  * Richetta and Odoni, (1993) Richetta, O. and Odoni, A. (1993).  Solving Optimally the Static Ground-Holding Policy Problem in Air Traffic Control.  Transportation Science, 27(3):228–238.
  * Shone et al., (2019) Shone, R., Glazebrook, K., and Zografos, K. (2019).  Resource allocation in congested queueing systems with time-varying demand: An application to airport operations.  European Journal of Operational Research, 276(2):566–581.
  * Shone et al., (2021) Shone, R., Glazebrook, K., and Zografos, K. (2021).  Applications of stochastic modeling in air traffic management: Methods, challenges and opportunities for solving air traffic problems under uncertainty.  European Journal of Operational Research, 292(1):1–26.
  * Simaiakis, (2013) Simaiakis, I. (2013).  Analysis, modeling and control of the airport departure process.  Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA.
  * Solak et al., (2018) Solak, S., Solveling, G., Clarke, J.-P., and Johnson, E. (2018).  Stochastic Runway Scheduling.  Transportation Science, 52(4):917–940.
  * Solveling et al., (2011) Solveling, G., Solak, S., Clarke, J.-P., and Johnson, E. (2011).  Runway operations optimization in the presence of uncertainties.  Journal of Guidance, Control and Dynamics, 34(5):1373–1382.
  * Stamatopoulos et al., (2004) Stamatopoulos, M., Zografos, K., and Odoni, A. (2004).  A decision support system for airport strategic planning.  Transportation Research Part C, 12:91–117.
  * Stolletz, (2008) Stolletz, R. (2008).  Non-stationary delay analysis of runway systems.  OR Spectrum, 30:191–213.
  * UK Aeronautical Information Services, (2019) UK Aeronautical Information Services (2019).  Aeronautical Information Circular P 092/2017.  https://www.skybrary.aero/bookshelf/books/1166.pdf.  Accessed on July 31, 2019.
  * Vossen et al., (2011) Vossen, T., Hoffman, R., and Mukherjee, A. (2011).  Air traffic flow management.  In: Barnhart, C. and Smith, B. (eds). Quantitative Problem Solving Methods in the Airline Industry: A Modelling Methodology Handbook. Springer, Boston, MA.
  * Zografos et al., (2017) Zografos, K., Madas, M., and Androutsopoulos, K. (2017).  Increasing airport capacity utilisation through optimum slot scheduling: review of current developments and identification of future needs.  Journal of Scheduling, 20(1):3–24.

Appendices

##  Appendix A The heuristic move operator $H$

Given a sequence $s$ of length $l$, the heuristic move operator $H$ works as
follows:

  1. 1.

Let $L:=l(l+1)/2$. We randomly select an integer $j\in\\{1,2,...,l\\}$ in the
following way: the probability of selecting 1 is $l/L$, the probability of
selecting 2 is $(l-1)/L$, and in general, the probability of selecting $p$ is
$(l+1-p)/L$ for $1\leq p\leq l$.

  2. 2.

The flight in position $j$ of $s$ is to be shifted by a certain number of
positions either forwards or backwards. First, decide on the direction of
movement using a simple ‘coin flip’, so that the ‘forwards’ and ‘backwards’
directions are selected with probability $0.5$ each.

  3. 3.

Let $P$ be sampled uniformly at random from the set $\\{1,2,3\\}$. The flight
in position $j$ of $s$ is removed from $s$ and then re-inserted at position
$\max\\{j-P,\;1\\}$ (if the ‘forwards’ direction was selected in step 2) or
position $\min\\{j+P,\;l\\}$ (if the ‘backwards’ direction was selected).

We note that if the integer $j$ selected in step 1 of the above procedure is
either $1$ or $l$, then there is a possibility that the ‘new’ sequence
generated is the same as the old one. However, the nature of how $H$ is used
in the SimHeur and DetHeur algorithms implies that the procedure will be
repeated as many times as necessary until the required number of distinct
sequences have been found.

##  Appendix B The method of pre-generating random events

The pre-generated sample path $\Omega^{\text{true}}$ includes complete
trajectories $\\{X_{i}(t)\\}_{t\in\mathcal{T}}$ for $i\in\mathcal{F}$, weather
forecast trajectories $\\{T_{0}(t)\\}_{t\in\mathcal{T}}$ and
$\\{T_{1}(t)\\}_{t\in\mathcal{T}}$, and a set of possible separation times
$\\{M_{ij}\\}$ for each $j\in\mathcal{F}$ (taking into account all
possibilities for the weight class of the predecessor flight $i$). The
approach for generating the trajectories $\\{X_{i}(t)\\}_{t\in\mathcal{T}}$
relies upon a time discretization. The steps are described below.

  1. 1.

For each $i\in\mathcal{F}$ we set the initial ETA, $X_{i}(0)$, as follows:

$X_{i}(0)=\begin{cases}a_{i}+\Delta_{i}^{\text{pre}}+\text{N}(0,\;\sigma_{i}^{2}|h_{i}|),&\text{if
}h_{i}<0,\\\ a_{i}+\Delta_{i}^{\text{pre}},&\text{if }h_{i}\geq 0,\end{cases}$

where $\text{N}(a,b)$ denotes a Normal random variable with mean $a$ and
variance $b$.

  2. 2.

We step forward in hundredths of a minute and, for each
$t=0.01,\;0.02,\;...,T$, generate the value $X_{i}(t)$ using a standard method
for simulating Brownian motion:

$X_{i}(t):=X_{i}(t-0.01)+\text{N}(0,\;0.01\times\sigma_{i}^{2}).$

We also define $X_{i}(u):=X_{i}(t-0.01)$ for $u\in[t-0.01,t)$.

The above method ensures that $X_{i}(t)$ is defined for all $t\in\mathcal{T}$
(it is a piecewise constant function of time). Although a time discretization
is used, the SimHeur and DetHeur algorithms may carry out system state updates
at any time $t$ in the continuous interval $\mathcal{T}$ (with $t$ depending
on the exact amount of CPU time spent on computations). In practice, this
means that the values $X_{i}(0)$, $X_{i}(0.01)$, $X_{i}(0.02)$, etc. are
stored inside an array and at time $t$, the algorithm looks up the value
$X_{i}(t^{\prime})$ where
$t^{\prime}:=\max\\{u\in\\{0,\;0.01,\;0.02,...,T\\}:u\leq t\\}$; for example,
if $t=2.764$ then we look up the value $X_{i}(2.76)$.

The steps for generating $\\{T_{0}(t)\\}_{t\in\mathcal{T}}$ and
$\\{T_{1}(t)\\}_{t\in\mathcal{T}}$ are very similar to the above, except we
set initial values $T_{0}(0)=t_{0}$ and $T_{1}(0)=t_{1}$ and use $\nu$ as the
variance parameter instead of $\sigma_{i}$.

In order to simulate separation times $M_{ij}$, we pre-generate a set of
values $\\{p_{j}^{\text{sep}}\\}_{j\in\mathcal{F}}$, with each
$p_{j}^{\text{sep}}$ being randomly sampled from a $\text{Uniform}[0,1]$
distribution. Then, once the weight class of the preceding flight $i$ becomes
known during the simulation, we calculate $M_{ij}$ by sampling the
$(p_{j}^{\text{sep}})^{\text{th}}$ quantile of the Erlang distribution for
$M_{ij}$.

##  Appendix C The mutation step

Given a sequence $s$ of length $l$, the steps used by the SimHeur and DetHeur
algorithms to perform a ‘mutation’ of this sequence at a particular time
$t\in\mathcal{T}$ are as follows:

  1. 1.

Let $M(t)$ denote the number of flights in $\mathcal{F}$ that have not yet
been added to the landing queue at time $t$; that is, $M(t)$ consists of
flights that are either still in the pool or yet to arrive in the pool.

  2. 2.

Let $P(t):=\min\\{4,\;Q(t)\\}$, where $Q(t):=\min\\{l,\;M(t)\\}$. Here, $P(t)$
is interpreted as the length of a particular subsequence within $s$ that we
want to ‘shuffle’ in order to obtain a new sequence.

  3. 3.

Define $R(t):=Q(t)-P(t)+1$ as the number of possible starting positions of the
string that we are going to shuffle.

  4. 4.

Let $L:=R(t)(R(t)+1)/2$. We randomly select an integer
$j\in\\{1,2,...,R(t)\\}$ in the following way: the probability of selecting 1
is $R(t)/L$, the probability of selecting 2 is $(R(t)-1)/L$, and in general,
the probability of selecting $p$ is $(R(t)+1-p)/L$ for $1\leq p\leq R(t)$.

  5. 5.

Consider the subsequence formed by taking the flights in positions
$j,\;j+1,...,j+P(t)-1$ of $s$. Remove all flights in this subsequence from
$s$, then ‘shuffle’ the subsequence, i.e. choose a random permutation of it.
Finally, re-insert the shuffled subsequence in the same position within $s$
that it occupied before.

Following these steps, we obtain a new sequence, interpreted as a ‘mutation’
of $s$.

##  Appendix D Obtaining the DStat policy

The heuristic method for obtaining the DStat policy referred to in Section 3.3
is as follows:

  1. 1.

We begin with a sequence $s_{0}$ of length $|\mathcal{F}|$ in which the
flights are ordered according to their ETAs following the realization of pre-
tactical uncertainty; that is, if flight $i\in\mathcal{F}$ appears before
flight $j\in\mathcal{F}$ then this implies $a_{i}+\Delta_{i}^{\text{pre}}\leq
a_{j}+\Delta_{j}^{\text{pre}}$.

  2. 2.

Set $s^{\text{best}}:=s_{0}$ and initialize a counter $c=0$.

  3. 3.

Set the pool arrival time to $Q_{i}=a_{i}+\Delta_{i}^{\text{pre}}-\tau$ for
all $i\in\mathcal{F}$, set $U_{0}=t_{0}$, $U_{1}=t_{1}$ and assume that all
separation times $M_{ij}$ conform to their expected values $E_{ij}(R_{j})$
(defined in (10)). For the release times $R_{j}$, we assume that each flight
$i$ in $s^{\text{best}}$ is released from the pool at the earliest possible
moment, with the restriction that flights must be released in the same order
that they appear in $s^{\text{best}}$. For example, if the 2nd flight in
$s^{\text{best}}$ happens to arrive in the pool earlier than the 1st flight,
then the 2nd flight should be released immediately after the 1st flight
arrives in (and is released from) the pool. We also define $A_{j}=R_{j}+\tau$
as the unconstrained arrival time of flight $j\in\mathcal{F}$, with the actual
landing time given by $L_{j}=\max\\{A_{j},L_{i}+M_{ij}\\}$, where $i$ is the
predecessor of $j$ in the queue. We then calculate the value of the objective
function (13) if the sequence $s^{\text{best}}$ is followed and let this be
denoted by $C^{\text{best}}$.

  4. 4.

Select a subsequence of 6 flights appearing consecutively in $s^{\text{best}}$
by sampling uniformly at random from the $|\mathcal{F}|-5$ possible
alternatives (corresponding to starting positions $1,2,...,|\mathcal{F}|-5$
within $s^{\text{best}}$).

  5. 5.

The subsequence selected in step 4 is removed from $s^{\text{best}}$ and the
flights in this subsequence are then ‘shuffled’; i.e. a random permutation of
the subsequence is chosen. The shuffled subsequence is then re-inserted into
$s^{\text{best}}$ in the same position that it occupied before. This yields a
new sequence that we refer to as $s^{\text{curr}}$.

  6. 6.

Calculate the value of the objective function (13) under the new sequence
$s^{\text{curr}}$ by setting the values of $Q_{i}$, $U_{0}$, $U_{1}$, $M_{ij}$
to their expected values and calculating $R_{i}$, $A_{i}$ as described in step
3. Let $C^{\text{curr}}$ denote the objective function value under
$s^{\text{curr}}$.

  7. 7.

If $C^{\text{curr}}<C^{\text{best}}$, then set
$C^{\text{best}}:=C^{\text{curr}}$ and $s^{\text{best}}:=s^{\text{curr}}$, and
set $c=0$. Otherwise, increase the counter $c$ by 1.

  8. 8.

If $c=10,000$, then terminate the procedure and accept $s^{\text{best}}$ as
the DStat policy. Otherwise, return to step 4.

Note that the final value of $C^{\text{best}}$ associated with the sequence
$s^{\text{best}}$ is not a measure of DStat’s actual performance, as
$C^{\text{best}}$ is based on the assumption of all random variables
conforming to their expected values. To evaluate DStat’s actual performance,
we must use the ‘real’ information contained in $\Omega^{\text{true}}$, as
explained in Section 3.3.

##  Appendix E Values of algorithmic parameters

In order to determine suitable values for the algorithmic parameters used by
the SimHeur and DetHeur algorithms, we conducted a preliminary computational
study to investigate sensitivity of the solutions with respect to these
parameter values. Tests were carried out using a small ‘test’ problem with a
time interval $\mathcal{T}$ of length 2 hours and a set $\mathcal{F}$
consisting of 60 flights with randomly-generated pre-scheduled arrival times
and weight classes. Based on the results of this study, we selected the
following parameter values:

  * •

(*) Default population size: $S=20$

  * •

(*) Default sequence length: $l=15$

  * •

(*) Minimum population size: $S_{\text{min}}=10$

  * •

(*) Threshold for performing mutations: $m_{\text{mut}}=25$

  * •

Threshold for performing ranking and selection: $r=50$

  * •

Threshold for releasing aircraft from pool: $n_{\text{rel}}=50$

  * •

Threshold for filtering population: $n_{\text{repop}}=500$

  * •

Maximum ‘idle runway probability’ for delaying pool release: $\lambda=0$

  * •

Step sizes for sequence cost estimates: $\psi_{n}=1/n$

The parameters marked (*) are used by both the SimHeur and DetHeur algorithms.
The others are used only by the SimHeur algorithm.


problem  Input: Question:

# Wooly Graphs : A Mathematical Framework for Knitting

Brian Bell
Department of Mathematics
University of Arizona
Tucson, AZ 85705
<EMAIL_ADDRESS>
& Kathryn Gray
Department of Computer Science
University of Arizona
Tucson, AZ 85705
http://rungray.github.io
<EMAIL_ADDRESS>
& Diana Sieper
Institute of Mathematics
Julius-Maximilians-Universität Würzburg
Würzburg, Germany
<EMAIL_ADDRESS>
& Stephen Kobourov
Technical University Munich
Munich, Germany
https://www.professoren.tum.de/en/kobourov-stephen
<EMAIL_ADDRESS>
& Falk Schreiber
Department of Computer and Information Science
University of Konstanz
Konstanz, Germany
<EMAIL_ADDRESS>
& Karsten Klein
Department of Computer and Information Science
University of Konstanz
Konstanz, Germany
<EMAIL_ADDRESS>
& Seokhee Hong
School of Computer Science
University of Sydney
Sydney, Australia
<EMAIL_ADDRESS>

(March 2024)

###### Abstract

This paper aims to develop a mathematical foundation to model knitting with
graphs. We provide a precise definition for knit objects with a knot theoretic
component and propose a simple undirected graph, a simple directed graph, and
a directed multigraph model for any arbitrary knit object. Using these models,
we propose natural categories related to the complexity of knitting
structures. We use these categories to explore the hardness of determining
whether a knit object of each class exists for a given graph. We show that
while this problem is NP-hard in general, under specific cases, there are
linear and polynomial time algorithms which take advantage of unique
properties of common knitting techniques. This work aims to bridge the gap
between textile arts and graph theory, offering a useful and rigorous
framework for analyzing knitting objects using their corresponding graphs and
for generating knitting objects from graphs.

##  1 Introduction

Knitting, an art form that weaves loops of yarn into intricate fabrics, has
long fascinated both artists and mathematicians. The patterns created through
knitting can be highly complex and often challenging to represent and analyze.
Recent advances [9, 6] have explored the potential of graphs to model and
understand these patterns, offering new perspectives and analytical tools. An
example of the knitting, yarn path, and graph can be seen in figure 1. This
paper aims to bridge the gap in the literature by discussing methods from
graph theory for identifying and categorizing graphs that represent knittable
patterns. By defining and analyzing knitting graphs, we can determine whether
a given graph corresponds to a knittable pattern. We further explore the
properties of these graphs, including Hamiltonian and Eulerian paths, and
propose a categorization of knitting techniques based on their graph
complexity.

$1$$2$$3$$7$$6$$5$$4$$8$$9$$10$$11$

Figure 1: A common ”Knit Front and Back” (kfb) stitch operation which
increases the number of stitches in a row by 1 is shown in knitting (left),
following the path of yarn (middle) and the resulting graph (right).

Through this exploration, we hope to provide a framework for understanding and
modeling knitting patterns using graph theory, contributing to both the
mathematical and artistic communities. In section 1.1, we discuss other crafts
that have been modeled by graphs, as well as some previous work on knitting.
In section 2.1, we define knitting and knitting graphs as well as define some
properties 2.2 and define categories of knitting 2.3. In section 3, we discuss
determining whether a graph is knittable and the uniqueness of a given graph
3.2. We give a discussion of the limitations of this approach in section 4 and
conclude in 5.

###  1.1 Related Work

Blackwork Embroidery is an embroidery technique that comes from England. It
can be modeled as a graph [13], and the paper goes over different properties
of Blackwork Embroidery graphs, including defining how the graph must be
Eulerian and has parity requirements on the edges.

Bobbin lace making has also been studied as it relates to graph theory [4].
The paper discusses how to identify a graph that could be a bobbin lace
pattern and generate the bobbin lace from it.

Hitomezashi, an embroidery technique from Japan, can be encoded using two
characters [23]. This paper also discusses the duality property of
Hitomezashi; a pattern on one side of the fabric corresponds to the reverse
pattern on the other. The authors note that this is also the case in knitting
patterns. This is explored with a problem on reversibility in “About Knitting”
[1].

Knitting itself has been studied by discussing knitting patterns in terms of
recursive knitting patterns [2] and how one could create a grammar around
knitting. This led to a definition of the Kolmogorov complexity for different
knitting patterns. This model was based only on knit and purl stitches,
looking at textures in knitting fabric.

Counts models knitting with directed graphs [6] with a focus on visualization
using a customized heuristic approach, as well as known graph embedding
methods such as multidimensional scaling [7, 24] and the Kamada-Kawaii
algorithm [16]. This approach has been further developed to better preserve
edge lengths and match considerations of knitting geometry [9]

Another way to model knitting is by looking at the individual building blocks
in terms of how the yarn is positioned [18]. This paper looks at the
topological construction of knitting and breaks it down to the smallest
repeatable section. While not about knitting, the book “Figuring Fibers”
contains a chapter [5] that discusses a method to understand intermeshed
crochet using graph theory. Here, we see the graphs used to understand how the
two meshes fit together. A planar graph that can be crochet will give its dual
as locations for the intermeshed portion.

A generative method for creating knitting patterns, KnitGIST[12], takes
different design considerations and stitch patterns to create hand-knitting
patterns. This work uses a knitting graph but focuses on creating knitting
patterns to fit a given stitch design and shape.

Many works look at machine knitting since it is usually easier to make things
at scale with this technique. One paper that starts to bridge the gap [11]
begins with hand knitting and converts to machine knitting. This paper also
creates methods to combine stitch techniques while keeping the general shape
and stretch of the fabric.

The modeling of knitting using finite automata has also been studied [10].
This focuses on machine knitting and the state of the needles and yarn in each
step.

Machine knitting has also been modeled using meshes [20]. Several rules for
their graphs we allow in our framework, such as no crossings. Since we are
focused on hand-knitting, we have different rules for what consists of
feasible knitting.

Another paper generates machine knitting patterns into arbitrary shapes using
the mesh technique [25]. This paper [26] creates a yarn-level visualization.
First, it generates a mesh that can correspond to different yarn positions.
Then, it relaxes these positions so that the yarn is in a more realistic
shape. This technique works for a variety of different stitches.

There is a paper looking at visually modeling knitting using edge length
forces and normal forces to look at different knitting structures [19]. This
paper begins with a stitch dictionary, defining how a mesh would be created
from this. They also give examples of three-dimensional structures.

##  2 Background and Preliminaries

In order to discuss knitting structures in detail, first we must carefully
defining knit objects and second, we must relate these objects with graph
models. Knitting objects have significant complexity depending on their
context [14, 13, 15]. In this study we will mostly consider the simplest
models necessary to capture structure of knitted objects. From a minimal
representation which treats each stitch as an infinitesimal vertex and its
connections with other stitches as abstract edges in a graph, we will add
complexity where necessary to examine knitting in other contexts, e.g. as
knots. We will however be omitting the level of detail both in diameter of
yarn and elastic properties necessary to analyze elastic properties of knit
fabric.

###  2.1 Basic Definitions

We will begin by describing knit objects with mathematical precision:

######  Definition 1 ($1$-Knit Object).

A _$1$ -knit object_ $O$ is an arrangement of interlocking loops in a single
piece of yarn such that connecting the two ends of the piece of yarn creates
the un-knot. Furthermore at least one loop must be secured only by another
loop passing through it.

This definition gives us the structure of knitting, loops or stitches, as seen
in Fig: 3. This figure shows a single row, in red, to show the path of the
yarn. In addition, we ensure that the knit object is not trivial by including
that we must have one loop secured only by another loop.

Now we will extend this definition by allowing more than one yarn. In
knitting, techniques using more than one yarn are common, including fair isle,
stripes, double knitting, intarsia, and other colorwork.

######  Definition 2 ($k$-Knit Object).

A _$k$ -knit object_ $O$ is a collection of $k$ yarns arranged into loops
which interlock and for which each independent yarn, joined end-to-end forms
the un-knot. Furthermore at least one loop must be secured only by another
loop passing through it.

Now we will explore a knit object that is finished. In knitting, a finished
object refers to an object that is closed so that it does not unravel. We will
show that this is a non-trivial.

######  Definition 3 ($1$-Knit Finished Object).

A $1$-Knit Finished Object is a 1-knit object which has been _finished_ such
that when the loose ends are connected it forms a non-trivial knot.

Generally, this is made by passing the ends of yarn from a knit object a
second time through their respective terminating stitches such that connecting
these ends forms an irreducible knot with O(n) crossings where $n$ is the
number of stitches. An example is shown in figure 2. In this figure, we show a
5-coloring of the knitted object, showing that it is not the unknot. In
general, the shape of a knit stitch allows us to color both legs in one color
and the piece behind with another. Then, we alternate these colors as we go up
the knitting. More colors are necessary at the beginning and end of the
knitting.

Figure 2: An example of a nontrivial knot formed by looping the loose ends of
yarn again through their respective stitches and then connecting them. We
color each stitch to show 5-colorability.

######  Definition 4 ($k$-Knit Finished Object).

A $k$-Knit Finished Object is a knit object which has been _finished_ such
that the loose ends of each piece of yarn can be connected to form (a) exactly
$k$ complex Brunnian Links or (b) $n$ knots where $0<n\leq k$ and $k-n$
unknots such that none of the unknots are free.

In case (a), we can construct a knit object such that the last unknot goes
through each stitch on the last row. The more general case (b), at least one
of the strands must not be the unknot. However many of these there are must
hold the rest.

From here, we can start to define a knitting graph. We begin by defining what
a vertex in relation to a knit stitch is.

######  Definition 5 (Knitting Vertices).

A _knitting vertex_ $v$ corresponds with one loop of yarn in a finished object
which is either closed or held by another stitch passing through it.

A knitting vertex can be thought of as a stitch in knitting. A closed stitch
occurs when one takes the tail end of the yarn and passes it directly through
the stitch. This keeps the loop from unraveling. Otherwise, the stitch will be
held by another stitch.

Now we can define a knitting graph made up of these vertices.

Figure 3: An example of how a single node connects to the rest of the knitting
graph. Here $S_{n}$ notes a single stitch with its connections. $S_{l}$ and
$S_{r}$ connect along the Hamiltonian path, which can also be seen in the red
strand. $S_{a}$ and $S_{b}$ connect through a loop connection.

######  Definition 6 (Knitting Graph).

A _knitting graph_ $G=(V,E)$ for a knit object $O$ is a simple graph
consisting of all knitting vertices $V$ and edges $E$ connecting each vertex
to any other vertex that: (1) is sequential along the yarn with this stitch or
(2) is passed through by this stitch.

We give an example of a single stitch with its graph connections in Fig: 3. In
that example, the two nodes to the right and left fall under (1), the stitches
are sequential along the yarn. We can see this by looking at the red thread.
The nodes above and below fall under (2), each of these stitches is connected
due to a stitch that is passed though. In the case of the node below, the
current node is passed through and in the case of the node above, the above
stitch is passed through the current node. In this way, we can create a
knitting graph from a knit object by creating the nodes and defining edges
based on the yarn connections. The sequential nature of stitches and the
dependency of each stitch on another also induces an ordering which we will us
later.

In addition, we can trace the path of the yarn through the knitting which
shows one strand of yarn along the sequential connections and two strands of
yarn for each of the vertical connections (one up, one down). We define a yarn
graph to model these connections.

Figure 4: An example yarn graph for simple stockinette knitting. Here, the
edges that are on the Hamiltonian are shown in black and the ones only on the
Eulerian (yarn) path are shown in blue

######  Definition 7 (Yarn Graph).

The yarn graph $Y=(V,E)$ for a knit object $O$ is a directed multi-graph
consisting of all knitting vertices $V$ for the object and edges with edges
$E$ for the path of the yarn as it passes through stitches.

######  Note 8.

The knitting graph is an un-directed subset of the yarn graph.

We can see an example of the yarn graph in Fig: 4. In this example, we see
that for each of the connections of type (2) in our knitting graph definition,
we have an edge to and from that node. These edges represent the loop, yarn
going to and from a given stitch.

Finally, we can compress the information from the yarn graph into a simple
directed graph by color-coding edges corresponding with whether they are of
type (1), i.e. single edges in the yarn graph, type (2), i.e. double edges in
the yarn graph, or a mix of both (e.g. the turn stitches on the edges). We
will use blue for type (1), red for type (2), and purple for mixed edges. This
is shown in figure 5. Formally:

######  Definition 9 (Directed Knitting Graph).

The directed knitting graph $B=(V,E,C)$ for a knit object $O$ is a directed
simple graph consisting of all knitting vertices $V$ for the object and edges
with directed edges $E$ colors (red, blue, or purple) $C$. This graph reduces
to the knitting graph for the same object by removing directions and colors.

Figure 5: Example graph modeling from [6] (colors adjusted) The blue edges
represent the yarn, the red edges represent interlocking (which is actually
creating the ‘real’ loops). Note purple edges are not visible in this section
since they only appear on the exterior where the rows increment.

###  2.2 Properties of Knitting Graphs

######  Theorem 10.

Every 1-knit object $O$ has a Hamiltonian path on its knitting graph $G$ and
its yarn-graph $Y$.

###### Proof.

Let $O$ be a 1-knit object with knitting graph $G$ and yarn graph $Y$. Since
$O$ must unravel and become the un-knot when the ends are tied together, we
will start at one end and follow the unraveling sequentially through each
stitch. This is the Hamiltonian path on $G$. Following the same path, since
the unraveling is sequential and exactly goes in the opposite of the yarn
direction, this also induces a Hamiltonian path through $Y$ in reverse of the
unraveling order. ∎

######  Note 11.

The gap between the knitting needles passes through each stitch exactly once
and thus follows the hamiltonian path induced by knitting an object.

######  Lemma 12.

Every 1-knit object $O$ has an eulerian path on its yarn grpah $Y$

###### Proof.

The the yarn induces a path through the yarn graph of the knit object, and
since there is exactly one piece of yarn and every section of yarn has exactly
one edge in the yarn graph, this path is Eulerian. ∎

######  Definition 13.

A simple graph $H$ is $k$-knittable if there exists a $k$-knit object $O$
whose knitting graph $G=H$.

######  Theorem 14.

Every graph with a Hamiltonian path is 1-knittable.

###### Proof.

Let $G=(V,E)$ be a planar graph with a Hamiltonian path $P_{G}$… (proof by
following the hamiltonian path and putting this stitch through any previous
stitches to which it is connected. The hamiltonian ordering prevents
collisions)∎

######  Lemma 15.

Every graph with a $k$-path cover k-knittable.

###### Proof.

Suppose $G$ has a $k$-path cover, then construct knit-objects for the subgraph
spanned by each path. Extend loops to connect the subgraphs. ∎

######  Lemma 16.

A graph is k-knittable if and only if it has a $k$-path cover.

###### Proof.

suppose it doesn’t have an $l$-path cover for $l\leq k$, then it cannot be
knit with $k$ pieces of yarn without introducing a new edge connecting at
least 2 of the paths in the cover, thus it cannot be knit with $k$ yarns.
Suppose a graph is $k$-knittable. Then each piece of yarn corresponds with a
path and since every stitch corresponds with a vertex, this induces a $k$-path
cover. ∎

###  2.3 Categorizing Knitting

Many knitting stitches and techniques exist, each bringing its own unique
qualities to the craft. Basic stitches like the knit and purl form the
foundation of most knitting projects, while more advanced techniques like
cabling create textured patterns resembling twisted ropes. Lace involves
creating delicate, openwork designs through a combination of increases and
decreases. Colorwork techniques, such as Fair Isle and intarsia, enable the
incorporation of multiple colors and yarns. Each of these methods expands the
creative possibilities in knitting, allowing crafters to produce everything
from simple to complex garments. Many of these techniques have bearing on our
ability to define the graphs corresponding to these objects. In this section,
we discuss how these techniques correspond to different classes of graphs. A
brief summary can be found in table 3.

We define the simplest knitting patterns and graphs with our complexity class
0. These correspond to planar graphs with restrictions enumerated in 6. In
knitting, this includes techniques such as knit and purl stitches, increases,
decreases, and simple lace. This does not include stitches which would knit
many stitches into many stitches (e.g. knit 3 together through the front and
back loop).

Figure 6: Allowed degree-distribution of the red edges.

Next, for class 1, we allow planar knitting without degree restrictions. This
includes many-to-many stitches.

Stitch | In Fabric | Subgraph | Classification
---|---|---|---
Knit (k) |  |  $1$$2$$3$$6$$5$$4$$7$$8$$9$ |  Class 0
Yarn over (yo) |  |  $1$$2$$5$$4$$3$$6$$7$$8$ |  Class 0
Knit Front and Back (kfb) |  |  $1$$2$$3$$7$$6$$5$$4$$8$$9$$10$$11$ |  Class 0
Knit Two Together (k2tog) |  |  $9$$10$$11$$8$$7$$6$$5$$1$$2$$3$$4$ |  Class 0
Cable One Behind (c1b) |  |  $1$$2$$3$$4$$8$$7$$6$$5$$9$$10$$11$$12$ |  Class 2
Table 1: Overview of output from all algorithms on general knitting patterns. The first column defines the knitting stitch we are looking at. The second column shows the actual knitted version. The boxed area is the stitch and outside is plain knitting. The subgraph column shows the graph of the stitch with some plain stitches around it. We color the stitches of interest and edges created in red to distinguish them. When knitting flat, rows alternate directions, we begin each diagram going left to right. In the last column, we define the lowest category that the stitch could be a part of. Note that the stitches may be used in fabric that is in a higher category, e.g. a knit stitch used in the same fabric as a star stitch, in which case the knitting fabric is defined as the highest category of any stitch. Stitch | Abbreviation | Strands of Yarn | Classification
---|---|---|---
Knit | K | 1 | Class 0
Purl | P | 1 | Class 0
Yarn Over | YO | 1 | Class 0
Knit Front and Back | KFB | 1 | Class 0
Knit Two Together | K2TOG | 1 | Class 0
Slip Slip Knit | SSK | 1 | Class 0
Make One | M1 | 1 | Class 0
Knit Three Together | K3TOG | 1 | Class 0
Bobble | B(n) | 1 | Class 1
Star Stitch | Star | 1 | Class 1
Knit One Below | K1B | 1 | Class 2
Knit One Slip One | K1SL1 | 1 | Class 2
Cable Two Behind | C2B | 1 | Class 2
Double Knit | DK | 2 | Class 3
Fair Isle | FI | 2 | Class 2
Intarsia | INT | 2 | Class 2
Brioche Knit | BRK | 1 | Class 2
Honeycomb Brioche Purl | HBP | 2 | Class 3
Table 2: List of knitting stitches and their abbreviations, required strands
of yarn, and full names, strands of yarn needed, complexity classification.

The next complexity class, class 2, describes knit objects whose graph
representation includes crossings and thus their edges must be labeled with an
orientation (e.g. front/back). This class of knitting includes cables, color
work, drop stitches, and many forms of brioche knitting. We can further refine
this class by exploring the $k$-planarity of the underlying knitting graph. We
define 1-planar knitting to be exactly all knit objects whose graphs are
1-planar. We can isolate two interesting subclasses based on the types of
edges crossed: 1a-planar knitting requires no crossings in edges corresponding
with stitches passing through other stitches (“vertical” edges). 1b-planar
knitting requires no crossings in edges corresponding with adjacency between
stitches (“horizontal” edges). Techniques corresponding to 1a-planar knitting
include colorwork where yarn color changes every other stitch, drop stitches
up to 1 row down, and simple brioche knitting. We note that brioche knitting –
which intentionally introduces extra crossings – includes at least one
technique which generate a maximally 1-planar graph when knitted in the round
as shown in Fig. 7. This technique uses 4 yarns to produce extra crossings.
1b-planar knitting includes single cables (see c1b in Table 1 which cross at
most 1 column.

$a$$b$$a$$b$$a$$b$$b$$a$$b$$a$$b$$a$$a$$b$$a$$b$$a$$b$

Figure 7: Brioche knitting pattern made by holding 4 strands of yarn in 2
colors. Note that exterior stitches on the sides are connected i.e. “in the
round.”

For $k>2$, we note that the reach of each non-planar technique is increased.
Each technique (colorwork, drop stitches, brioche techniques, and cables) has
its reach increased by at least $k$ and as much as $2k$, meaning that drop
stitches can drop at least $k$ rows down and possibly up to $2k$ rows,
depending on the rest of the graph. There is a natural layout of each graph
which corresponds to the plane in which it was knit. In this layout, the
number of crossings introduced by each technique can be exactly determined by
the parameters of the technique. For example in a cable 8 back (c8b), 8
stitches are removed from the needle and held to the back of the knitting
while the subsequent 8 stitches are knit and then returned to the needle to be
knit. This introduces 8 crossings in the natural knitting layout. However, a
different layout may be found which introduces other crossings not naturally
in the knitting in order to reduce the number of crossings corresponding with
the cable in another layout.

The complexity class 3 corresponds to knit objects whose vertices also require
multiple orientations. This class includes double-knitting, where two layers
of fabric (front and back) are knit simultaneously with two yarns allowing the
yarns to be swapped arbitrarily between the front and back. This allows for
very sophisticated color work and produces a thicker combined fabric. Other
techniques, including some forms of brioche, also fit this classification.
Depending on the level of detail required, this class of knitting may require
3D layouts or impose stronger requirements on 2D layouts for visualization.

We can get some insight into these classes by looking at a popular knitting
and crochet website, Ravelry [22]. Ravelry has a search function where you can
look through hundreds of thousands of patterns. Of these, about 240,000 are in
class 0, 16,000 in class 1, 105,000 in class 2, and 6,000 in class 3. Some
examples of stitches which delineate the differences between these classes are
shown in 2. This quick look did not include every pattern on Ravelry since
Ravelry’s categories are optional for patterns and some categories on Ravelry
could fall into multiple classes.

Complexity | Knit Description | Graph Description
---|---|---
0 | Basic Simple Knitting | planar graphs with restrictions from 6
1 | Common simple knitting | planar graphs
2 |  $k$-planar knitting |  Edges have Two Orientations (cables, colorwork, brioche)
3 | Double Knitting |  Edges and Nodes have multiple orientations
Table 3: Description of categories of knitting in relation to their graph
description.

##  3 Identifying Knittable Graphs

Now that we have labeled different types of knitting, we will focus on
identifying which graphs are knittable in the various complexity classes that
we have defined. We will start with the general graph case.

######  Lemma 17.

Identifying general $k$-knittable graphs is NP-hard.

###### Proof.

Let $G$ be a graph. By Lemma 16, $G$ is k-knittable iff $G$ has a $k$-path
cover. Determining whether $G$ has a $k$-path cover is NP-hard [17]. ∎

###  3.1 Identifying $k$-knittable DAGs.

If we have more information on the graph and know that it is a DAG, we can
identify a knittable graph easier. We start with the definition of a
$k$-knittable DAG.

######  Definition 18.

A directed graph $H$ is $k$-knittable if there exists a coloring $C$ and a
$k$-knit object $O$ whose directed knitting graph $G=H\bigoplus C$.

######  Theorem 19.

1-knittable DAGs can be identified in linear time.

We can find a Hamiltonian path, if it exists, in linear time. By sorting the
nodes topologically, we end up with an ordering for the Hamiltonian path. As
shown above, given a Hamiltonian path, we can construct a knitting pattern, by
setting every edge not on the Hamiltonian to a loop connection. ∎

######  Note 20.

If there are restrictions on the edge connections, we can check this as we
build the Hamiltonian by checking the in and out degrees.

Likewise, a $k$-knittable DAG follows similarly.

######  Theorem 21.

$k$-knittable DAGs can be identified in polynomial time.

This is equivalent to finding a k-disjoint-path-cover, which has been studied
in a variety of settings. It has been shown to be parameterized linear [8],
although the general algorithm is polynomial through a reduction to minimum
flow [21].

######  Theorem 22.

It can be decided in polynomial time, whether a DAG is $k$-knittable with no
violet edges, and of complexity class 0.

###### Proof.

When deciding whether a DAG $G=(V,E)$ is $k$-knittable, the task is to color
the edges blue or red in such a way the blue edges form at most $k$ directed
paths, and the red edges fulfill the degree restrictions for every vertex. In
order to test this we generate a flow network for $G$ in which a valid flow of
value $k$ will represent the $k$ threads. For every vertex $v$, we can decide
whether it can be the start of a thread ($S$), at the end of a thread ($T$),
in the middle ($M$) or any combination of these simply by looking at the in-
and outdegree of $v$. We define $S\subseteq V$ to be the vertices $v\in V$,
such that $\mathrm{indeg}(v)$ and $\mathrm{outdeg}(v)-1$ fulfill the red
degree restrictions. Next, we define $M\subseteq V$ ($T\subseteq V$) to be the
vertices, such that $\mathrm{indeg}(v)-1$ and $\mathrm{outdeg}(v)-1$
($\mathrm{indeg}(v)-1$ and $\mathrm{outdeg}(v)$) fulfill the red degree
restriction. Note that this $M$, $S$ and $T$ are generally partially
overlapping. Further, if there is any vertex that is in none of the sets $M$,
$S$ and $T$, the solution is infeasible. Table 4 sums up in which sets a
vertex is, based on its degrees,

Indeg | 0 | 1 | 2 | $\geq 3$
---|---|---|---|---
Outdeg |  |  |  |
0 | non-feasible | non-feasible | $S$ | non-feasible
1 | non-feasible | non-feasible |  $M$, $T$ | $T$
2 | $S$ |  $S$, $M$ |  $S$, $M$, $T$ | $M$
$\geq 3$ | non-feasible | $S$ | $M$ | non-feasible
Table 4: Combinations of in- and outdegrees and their implications on
feasibility for Theorem 22.

We generate a flow graph $G_{F}$ out of $G$. First, we split every vertex $v$
into two vertices $v_{\mathrm{in}}$, $v_{\mathrm{out}}$. If $v\in M$, we
assign all incoming edges of $v$ to $v_{\mathrm{in}}$, all outgoing edges to
$v_{\mathrm{out}}$, and we add a new directed edge from $v_{\mathrm{in}}$ to
$v_{\mathrm{out}}$, to which we assign a minimum and a maximum flow of one
(enforcing that precisely one unit of flow and thus one thread will contain
$v$). Note that if $v\notin M$, then either $v\in S$ or $v\in T$. If $v\in S$,
we only assign the outgoing edges of $v$ to $v_{\mathrm{out}}$ (with maximum
capacity 1), but we omit assigning the incoming edges of $v$. Similarly, if
$v\in T$, we only assign the incoming edges of $v$ to $v_{\mathrm{in}}$ (with
maximum capacity 1), but we omit assigning the outgoing edges of $v$. We add
two new source-vertices $s_{\mathrm{in}}$ and $s_{\mathrm{out}}$, and connect
$s_{\mathrm{in}}$ to $s_{\mathrm{out}}$ via a directed edge with capacity of
precisely $k$ (ensuring that any valid flow will have a value of precisely
$k$, ensuring that precisely $k$ threads are used). Further, we add edges from
$s_{\mathrm{out}}$ to every vertex $v\in S$ with maximum capacity 1.
Similarly, we add two new sink-vertices $t_{\mathrm{in}}$ and
$t_{\mathrm{out}}$, and connect $t_{\mathrm{in}}$ to $t_{\mathrm{out}}$ via a
directed edge with capacity of precisely $k$. Further, we add edges from every
vertex $v\in T$ to $t_{\mathrm{in}}$ with maximum capacity 1. All edges that
were originally present in $G$ get assigned a maximum capacity of 1.

Given an s-t-flow $F$ for $G_{F}$, we can extract $k$ threads that cover $V$
by following the flows that leave $s_{\mathrm{out}}$ until they arrive at
$s_{\mathrm{in}}$, taking for every unit of flow all vertices $v$ for which
this unit uses the edge $(v_{\mathrm{in}},v_{\mathrm{out}})$ in this order.

Then, since for every $v\in V$ the minimum and maximum capacity of
$(v_{\mathrm{in}},v_{\mathrm{out}})$ is precisely 1, every vertex is covered
by precisely one thread. Also, we ensured that only vertices that are in $S$
can be the start of a thread, and only vertices that are in $T$ can be the end
of a thread. Further, since for every vertex $v\notin M$ we either added only
outgoing edges or only incoming edges apart from the edges from/to
$s_{\mathrm{out}},t_{\mathrm{in}})$, none of these vertices can be in the
middle of a thread. Thus, the degree constraints are fulfilled for every
vertex.

By taking a thread cover of $G$ of size $k$, we can construct a valid flow for
$G_{F}$. ∎

###  3.2 Edge Cases

######  Theorem 23.

Each isomorphically distinct Hamiltonian path gives a different knit object.

###### Proof.

Given two isomophically distinct Hamiltonian paths, with nodes $H1_{1}\dots
H1_{n}$ and $H2_{1}\dots H2_{n}$, there must be edges $(H1_{k},H1_{j})$ that
correspond to $(H2_{m},H2_{n})$. Since $k\neq m$ and $j\neq n$, the looped
stitches will be attached in different places. This gives two different
knitted object.∎

In terms of a DAG, only one Hamiltonian path is possible, which reduces the
total number of knit objects. However, if we do not have a DAG, the number
reduces to finding Hamiltonian paths and is NP-Hard.

######  Theorem 24.

The number of rows which can be knit [using basic knitting stitches] for a
1-knittable object which has a planar directed knitting graph can be computed
in linear time.

###### Proof.

Given a planar directed knitting graph corresponding with a 1-knittable
object, we can follow a topological ordering (this will follow the Hamiltonian
path of the needles through the object). Starting with our first source in the
topological ordering, since the graph is planar, we can label all edges
originating from this vertex which are not part of the hamiltonian path
“left”. Now, we will proceed until a source edge appears on the opposite side
which we will call “right”. Each time the side switches, we will add another
row. Since the graph is planar and we have incremented rows each time, we have
not violated the conditions for basic knitting. This can be seen if we look at
book embeddings of planar, Hamiltonian graphs. It is well known that such
graphs have a book embedding of 2 pages [3], now whenever a node’s outgoing
edges switch sides, we define this as the next row in knitting. ∎

This does gives some ambiguous cases when nodes do not contain outgoing edges.
Either a row switch or maintaining the same row would be acceptable, we would
suggest keeping the row to minimize the number of row switches.

##  4 Discussion and Limitations

We model knitting with a discrete structure, while knitting itself consists of
a continuous yarn. This gives us a way to model the knitting, however, it may
not model everything that we would want in the knitting. For example, the
stretch of the knitting due to the yarn is not modeled in the graph form. A
more sophisticated model will be necessary to study elasticity which is a
direction for future work.

We create several classes of knitting, which we believe covers most knitting
stitches. There are many different stitch varieties and while we believe all
of them can fit into these categories there may be stitches that require a new
category.

Our graph representation of knitting is referenced to the top of each knit
loop which leaves an ambiguity about how the graph should be indexed
especially with regards to the cast-on row and edges.

While we discuss how knit and purl stitches are different and result in
different orientations in the yarn graph, we do not explore how this affects
the fabric. Looking at the reverse of the knit fabric and modeling the
different sides with different edge orientations is an interesting future
work.

Exploring how cables affect the space of the knitting is a future direction
that can allow us to understand the topology of graphs as well.

Finally, double knitting and brioche are two techniques that have interesting
structure and many knitting patterns and techniques associated with them.
Creating graphs to model these specific stitches can give us a better
understanding of knitting and possible yarn connections.

##  5 Conclusions and Future Directions

This paper looks at different models of knitting using graphs. We have defined
several categories of knitting that correspond to different types of graph.
These categories also follow general knitting wisdom of complexity. From this
point, we determine several properties of graphs that are necessary for them
to be knitting graphs. We discuss the uniqueness of knitting graphs and how
many knitting patterns we could have from one graph.

While we look at each of these things for some of our classifications, there
are many open questions in this direction. For example, double knitting has
some very strict structural requirements. Defining and modeling these in terms
of the necessary covers and node connections is an interesting problem.
Likewise, brioche has complex yarn and knitting connections that would lead to
some interesting algorithms. Finally, measurement of elasticity of knit fabric
is a well motivated future work which we hope can be built on top of our
framework with some additional modeling information.

## References

  * [1] Sarah Marie Belcastro and Carolyn Yackel.  About knitting ….  Math Horizons, 14(2):24–39, 2006.
  * [2] Anna Bernasconi, Chiara Bodei, and Linda Pagli.  On formal descriptions for knitting recursive patterns.  Journal of Mathematics and The Arts, 2:9–27, 03 2008.  doi:10.1080/17513470802165000.
  * [3] Frank Bernhart and Paul C Kainen.  The book thickness of a graph.  Journal of Combinatorial Theory, Series B, 27(3):320–331, 1979\.  doi:https://doi.org/10.1016/0095-8956(79)90021-2.
  * [4] Therese Biedl and Veronika Irvine.  Drawing bobbin lace graphs, or, fundamental cycles for a subclass of periodic graphs.  In Fabrizio Frati and Kwan-Liu Ma, editors, Graph Drawing and Network Visualization, pages 140–152, Cham, 2018. Springer International Publishing.
  * [5] Kyle Calderhead, Carolyn Yackel, and Sarah-Marie Belcastro.  Gosper-like fractals and intermeshed crochet, page 31–56.  American Mathematical Society, 2018.
  * [6] Jared B Counts.  Knitting with directed graphs.  Master’s thesis, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, 2018.
  * [7] Anthony Peter Macmillan Coxon and CL Jones.  Multidimensional scaling.  Essex University/European Consortium for Political Research, 1972.
  * [8] Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, and Alexandru I. Tomescu.  Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 359–376. ACM-SIAM, 2022.  doi:10.1137/1.9781611977073.18.
  * [9] Kathryn Gray, Brian Bell, and Stephen Kobourov.  A graph model and a layout algorithm for knitting patterns, 2024.  URL: https://arxiv.org/abs/2406.13800, arXiv:2406.13800.
  * [10] S.A. Grishanov, T. Cassidy, and D.J. Spencer.  A model of the loop formation process on knitting machines using finite automata theory.  Applied Mathematical Modelling, 21(7):455–465, 1997.  doi:https://doi.org/10.1016/S0307-904X(97)00042-5.
  * [11] Megan Hofmann, Lea Albaugh, Ticha Sethapakadi, Jessica Hodgins, Scott E. Hudson, James McCann, and Jennifer Mankoff.  Knitpicking textures: Programming and modifying complex knitted textures for machine and hand knitting.  In UIST ’19, page 5–16, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3332165.3347886.
  * [12] Megan Hofmann, Jennifer Mankoff, and Scott E. Hudson.  Knitgist: A programming synthesis toolkit for generating functional machine-knitting textures.  In Proceedings of the 33rd Annual ACM Symposium on User Interface Software and Technology, UIST ’20, page 1234–1247, New York, NY, USA, 2020. Association for Computing Machinery.  doi:10.1145/3379337.3415590.
  * [13] Joshua Holden.  The graph theory of blackwork embroidery.  In S.M. Belcastro and C. Yackel, editors, Making Mathematics with Needlework: Ten Papers and Ten Projects. CRC Press, 2007.  URL: https://api.semanticscholar.org/CorpusID:55364854.
  * [14] Paul C. Kainen and Shannon Overbay.  Graph embeddings with no hamiltonian extensions, 2023.  arXiv:2303.08306.
  * [15] Jonathan M. Kaldor, Doug L. James, and Steve Marschner.  Simulating knitted cloth at the yarn level.  In ACM SIGGRAPH 2008 Papers, SIGGRAPH ’08, New York, NY, USA, 2008\. Association for Computing Machinery.  doi:10.1145/1399504.1360664.
  * [16] Tomihisa Kamada and Satoru Kawai.  An algorithm for drawing general undirected graphs.  Information processing letters, 31(1):7–15, 1989.
  * [17] Richard M Karp.  Reducibility among combinatorial problems.  Springer, 2010.
  * [18] Shashank Markande and Elisabetta A. Matsumoto.  Knotty knits are tangles on tori.  arXiv: Soft Condensed Matter, 2020.  URL: https://api.semanticscholar.org/CorpusID:211031926.
  * [19] Sasha McKinlay and Skylar Tibbits.  Visualization of three-dimensional knit textiles.  ACADIA, 2023.
  * [20] Vidya Narayanan, Lea Albaugh, Jessica Hodgins, Stelian Coros, and James Mccann.  Automatic machine knitting of 3D meshes.  ACM Trans. Graph., 37(3), aug 2018.  doi:10.1145/3186265.
  * [21] S.C. Ntafos and S.L. Hakimi.  On path cover problems in digraphs and applications to program testing.  IEEE Transactions on Software Engineering, SE-5(5):520–529, 1979\.  doi:10.1109/TSE.1979.234213.
  * [22] Ravelry.  URL: http://ravelry.com/.
  * [23] Katherine A. Seaton and Carol Hayes.  Mathematical specification of hitomezashi designs.  Journal of Mathematics and the Arts, 17:156–177, 2022.  URL: https://api.semanticscholar.org/CorpusID:251881630.
  * [24] Warren S. Torgerson.  Multidimensional scaling: I. theory and method.  Psychometrika, 17(4):401–419, 1952.
  * [25] Kui Wu, Hannah Swan, and Cem Yuksel.  Knittable stitch meshes.  ACM Trans. Graph., 38(1), jan 2019.  doi:10.1145/3292481.
  * [26] Cem Yuksel, Jonathan M. Kaldor, Doug L. James, and Steve Marschner.  Stitch meshes for modeling knitted clothing with yarn-level detail.  ACM Trans. Graph., 31(4), 2012.  doi:10.1145/2185520.2185533.


# Automatic Identification and Ranking of Emergency Aids in Social Media Macro
Community

Bhaskar Gautam  0000-0002-3258-9927 Data Informatics and Analytics Lab
National Institute of Technology, KarnatakaP.O.
SrinivasnagarSurathkal-575025India575025<EMAIL_ADDRESS>and
Annappa Basava  Data Informatics and Analytics Lab
National Institute of Technology, KarnatakaP.O.
SrinivasnagarSurathkal-575025India575025<EMAIL_ADDRESS>
###### Abstract.

Online social microblogging platforms including Twitter are increasingly used
for aiding relief operations during disaster events. During most of the
calamities that can be natural disasters or even armed attacks, non-
governmental organizations look for critical information about resources to
support effected people. Despite the recent advancement of natural language
processing with deep neural networks, retrieval and ranking of short text
becomes a challenging task because a lot of conversational and sympathy
content merged with the critical information. In this paper, we address the
problem of categorical information retrieval and ranking of most relevance
information while considering the presence of short-text and multilingual
languages that arise during such events. Our proposed model is based on the
formation of embedding vector with the help of textual and statistical
preprocessing, and finally, entire training 2,100,000 vectors were normalized
using feed-forward neural network for need and availability tweets. Another
important contribution of this paper lies in novel weighted Ranking Key
algorithm based on top five general terms to rank the classified tweets in
most relevance with classification. Lastly, we test our model on Nepal
Earthquake dataset (contains short text and multilingual language tweets) and
achieved 6.81% of mean average precision on 5,250,000 unlabeled embedding
vectors of disaster relief tweets.

Automatic Information Retrieval Model, Transliteration, Multilingual Language,
Embeddings, Multi-layer Perceptron, w-Ranking Key Algorithm

††copyright: none††conference: ACM FIRE conference; Bangalore; India††ccs:
Information systems Data stream mining††ccs: Information systems Data
Cleaning††ccs: Information systems Clustering and Classification††ccs: Human-
centered computing Social tagging systems

##  1\. Introduction

The branch of Information-driven and computational social science research is
growing in importance (Lazer et al., 2009), and with this trend, there is a
need of common fully-automatic information retrieval model to facilitate a
robust and reproducible research environment (Han Veiga and Eickhoff, 2016).
Initially, Online Social Networks (OSNs) aims to allow users to communicate,
connect with others and share content (Eriksson and Olsson, 2016) but nowadays
the OSNs allows its users to broadcast personal thoughts and content. During
natural or man-made disasters, these social networks provide the rich source
of near-real-time data streams which helps in the formation of emergency
situation summarization (Rudra et al., 2016). However, increasingly usage of
these social media tweets for aiding relief operations during disaster events
such critical information is usually submerged with a lot of conversational
content, such as sympathy for the victims of the disaster. Hence, automated
Information Retrieval techniques are needed to extract availability and
absence of any kind of resource to save life.

In this paper, we focus on automatic classification and ranking problem (Nazer
et al., 2016; Rudra et al., 2015) for two types of critical information, named
as Need-tweets and Availability-tweets. Our goal is to improve classification
methods and return the tweet in most relevance order with the class while
considering the fact of the presence of short-text and multilingual language
in OSNs. A glimpse of the challenge described in FIRE 2017 Information
Retrieval from Microblogs during Disasters Track
111https://sites.google.com/site/irmidisfire2017/ and also discussed in (Basu
et al., 2017). Training and evaluation of the entire model is done using
70,000 tweets which were posted during the 2015 Nepal earthquake. However,
including the need and availability tweets corpus also include some redundancy
such as the presence of similar tweets and all such false tweets were removed
by Track organizers as discussed in (Khosla et al., 2017) in order to preserve
uniqueness of tweet labels. The purpose of this paper is to consider the
highlighted problem, and the trade-offs that they entail. Our paper makes the
following contributions (1) We describe the methodology and (2) release the
pseudo code in order to replicate the results of entire paper. The remainder
of this paper is structured as follows: in Section 2, we present the Feature
resolution methods used to create a feature vector for neural network model.
Section 3 presents methodology followed in the formation of entire information
retrieval model. Section 4 discusses the task required to form classification
model. Section 5 discusses the weighted ranking key algorithm and Section 6
depicts about the evaluation and result of the model while comparing with
another team. Finally the paper concludes in Section 7 with discussing some of
the conceivable use cases.

##  2\. Feature Resolution Methods

In this section, we discuss the Feature Resolution Methods which helps in the
formation of embedding vectors proposed to consumed by our classification
model. The methods are - Textual preprocessing and Statistical Preprocessing
which exploits the public information of social network users with the help of
Stanford NLP Toolkit 222https://nlp.stanford.edu while preserving privacy. A
detailed description of each method is elaborated in following sections.

###  2.1. Textual Preprocessing

The goal of this phase is to make all tweets in a particular semantics some of
them are discussed in (Purohit et al., 2013; Hürriyetoglu and Oostdijk, 2017)
considering the tweet which are written in a language (specifically English,
Hindi, Nepal, and language which is the combination of Hindi + English).
Tweets are represented as vectors of features, each feature being a word
unigram, by performing standard text preprocessing operations whose highlights
are depicted as follows:

  * •

Removing non-ASCII characters.

  * •

Removing all the stopwords (also for Hindi and Nepali).

  * •

Normalizing all the text of tweets into lowercase.

  * •

ASCII transliterations of Unicode text (Tweet).

  * •

Separation of sentence into tokens (words)

  * •

Stemming of social media tweets using the standard Porter stemmer.

###  2.2. Statistical Preprocessing

During Disaster-related crises, the social media tweets which belonged to the
same context generally submerged with interrelated keywords which summarized
the entire tweet (are discussed in Table 1) and referred in the rest of the
paper. These keywords consist of tweets which describe the resource
availability status and moreover the need of the resources.

Table 1. Description of Top five keywords available in Corpus Keyword | Description | Annotation
---|---|---
Question | Request for any resources | $\beta_{need}$
Link | Offer availability of resource using portal |  $\gamma_{need}$, $\beta_{availability}$
Hash | Broadcast availability of resource using all popular Hashtags | $\gamma_{availability}$
Mention | Offer some help while publicizing particular community (Political Party etc.) | $\alpha_{availability}$
Number | With Mobile number offer help (Ambulance etc.) | $\alpha_{need}$
QuestionLinkHashMentionNumber$0$$500$$1{,}000$$1{,}500$Cumulative Frequency of
keywordsAvailabilityNeed Figure 1. Statistical Relationship of top 5 Features
among different social media macro community category in entire training
corpus

The contribution of these keywords are described in Figure 1, where
Availability Tweets have the maximum contribution. To have reflection of these
tokens in tweet, we generalize some tokens by replacing ? by the token
QUESTION, hyperlinks by the token LINK, Hashtag by the token HASH, MENTION
token is the replacement of (@username) and lastly, any number of the tweets
are replaced by NUMBER.

##  3\. Methodology

Most of the users in Online Social Network (specifically, Twitter) share
personal information, random thoughts, opinions/complaints and facts (Naaman
et al., 2010). Moreover, with in near-real-time these social network explodes
with an activity whenever any calamity takes place (Dewan et al., 2016).
Considering above statements as a hypothesis for this paper, we combine the
discussed feature resolution methods to create a fully-automated system, named
as Categorical Information Retrieval (IR) and outlined in architecture Diagram
2. Given the social networking post (tweet, that are associated with the
related hashtag), the Categorical IR initiates with the formation of two
feature vectors termed as Textual preprocessing and Statistical Preprocessing.

Social Networking PostTextual preprocessingStatistical preprocessingClassifier
ModelClassified TweetsNeedy Tweet RankAvailability Tweet Rank Figure 2.
Architecture and Methodology of Categorical IR

The formation of these feature vectors are essential as it normalizes the
semantics of the given post. These preprocessed posts are transformed into
embedding (Le and Mikolov, 2014) vectors of size 100 and 5 in length
respectively. Once the initialization of entire embedding are done, our
classification model (further elaborated in Section 4) precisely able to
categorize any tweets with respect to its relevance with the help of these
embeddings. After enforcing these requirements, our Ranking algorithm will
precisely rank the classified tweet irrespective of any language within a
relevance class.

##  4\. Classification Model

Classification model initiates with the formation of words embeddings for
every social media tweet using Textual preprocessing with the help of Doc2vec
model(Le and Mikolov, 2014), well suited for variable length and short length
text which outperforms the Word2vec model and probabilistic latent semantic
analysis model approach discussed in (Khosla et al., 2017; Nguyen et al.,
2016; Gupta et al., 2013). Now, each of the word embedding (of size 100 in
length) combines another feature vector which was formed using the frequency
of each token (discussed in Section 2.2) available in a tweet. After
preprocessing, we have one entire embedding vector of length 105 which will be
the final representative of the respective class.

Social media tweets in entire training corpus are transformed into 21,00,000
vectors (each of length 105) in which the absence of most similar tweets are
ensured by the track organizers. These embeddings will be the input for
multilayer preceptron (a feedforward Artificial Neural Network model).
Multilayer preceptron model runs upto 300 iterations with an “ReLu” as a
activation function. During the training of model, entire training embedding
vectors (2,100,000) were cross-validated with K-folds (k=10), and gives
maximum precision and recall in comparison with Naive Bayes, Logistic
Regression, SVM even with Random Forest including F-Score.

##  5\. Category Based Ranking

Classification model effectively classifies each social media tweet to the
respective class and each classified tweet along with the prediction score
(termed as $score_{need}$ and $score_{availability}$) are collected separately
as depicted in Figure 2. With the weighted(w)-Ranking Key algorithm, we
transform the probability of tweet belong to relevance class with the rank
score (termed as $Rank_{score}$). Ranking of tweets based on $Rank_{score}$
helps in prioritizing tweets with most relevant to class considering the
presence non relevance tweets.

###  5.1. w-Ranking Key Algorithm

w-Ranking Key Algorithm proceeds with the initialization of two buckets of top
20 keywords from each relevance class of tweets available in “Classified
Tweet” using Twitter LDA (TLDA) topic modeling model which already outperforms
the state-of-the-art model on news corpora discussed in (Fang et al., 2016;
Zhao et al., 2011) and in rest of the paper, we refer these bucket as a
$K_{20}-Need$ and $K_{20}-Availability$ respectively. To provide more weights
to tweets which contain keywords as described in Table 1, we have created two
more small buckets labeled them as $H_{5}-Need$ and $H_{5}-Availability$
respectively. Moreover, each keyword is classified into most relevance class
and annotation of each keyword with respect of class also shown in Table 1.
You may note that each keyword can be assigned to more than one category, as
the corresponding keyword could belong to more than one category.

For each classified tweet, algorithm makes count the presence of each
annotated keyword with $\alpha_{1},\alpha_{2},\text{ and }\alpha_{3}$. We pool
the relevance class score with the updated relevance class score. Now, if the
similarity score between the word available in each tweet and the tokens
available in buckets ($H_{5}$ and $K_{20}$ of category) exceeds a certain high
confidence threshold C, we exponentially upgrades the pool score with itself
(and hence it provides the more weight to keyword which is most relevant). For
our similarity metric between keywords, Levenshtein Distance (named after
Vladimir Levenshtein, 1965) is preferable among another more obvious candidate
in string similarity metrics considering the presence of short text language
used in a tweet. Moreover, the algorithm assigns negative weights to the tweet
which contains most common keywords available in a most non-relevance tweet
such as ”quake” and any floating-point number. Entire pseudo code of algorithm
is discussed in Appendix A.

##  6\. Evaluation and Results

Primarily, the motivation for this paper is to get a quick overview of the
current fully-automated state-of-the-art models for disaster reliefs for
various countries. We reviewed several Information Retrieval (IR) models but
none of them have the better precision for short text and multilingual
languages. In this section, we highlight the precision and recall of our
proposed fully-automatic IR model for disaster reliefs (obtained with the
prediction of class and ranking for 50,000 tweets).

Precision<EMAIL_ADDRESS>Results estimated by
organizersAvailability: DIA_LAB_NITKAvailability: NU_TeamNeed:
DIA_LAB_NITKNeed: NU_Team Figure 3. Performance evaluation of classification
model (including Ranking Key Algorithm) in terms of Precision with top 100
ranked tweets and Recall with top 1000 ranked tweets including comparison of
results with another team.

The performance evaluation of model shown in Figure 3 while comparing the
evaluation results with another Team (NU_Team) participated in track.
Different evaluation metrics (such as precision, recall) and measures were
used on top 100 and 1000 tweets (ranked by our algorithm) respectively.
Finally with the help of mean average precision results were evaluated while
comparing with a gold-standard dataset of Nepal Earthquake.

##  7\. Conclusions and Future work

In this paper, we addressed the problem of categorical information retrieval
and ranking model for disaster relief while considering the presence of short-
text and multilingual languages. In such a scenario, we can expect to have a
lot of conversational and sympathy content submerged with the critical
information. Moreover, most of the critical information on Online Social Media
regarding disaster relief are either in form of short-text or in local
regional language. Hence, Our fully-automated Categorical information
retrieval model for disaster relief integrates textual and statistical
preprocessing methods. Through the combination of textual and statistical
embeddings we train our model with a multi layer preceptron model with the
presence of 76% Availability Tweets and 23% of Need Tweets achieved 6.81% of
mean average precision on 50,000 unlabeled disaster relief tweets. Categorical
model can be used in evaluation of number available resources with need of
resource ultimately it helps in reducing the load on public emergency services
and coordinate social effort to save lives. Our experiments on Twitter data
from Nepal Earthquake dataset strongly indicates that the proposed fully-
automated supervised approach could most often result in improving the
accuracy as compared to state-of-the-art approaches and produces the similar
result on other dataset even on real time streaming. We plan to extend our
approach with deep residual networks and with this strategy it is expected to
result in further improvement in precision and recall of architecture.

##  Appendix A Appendix

$\lambda_{Need}\leftarrow\max(score_{need})$

$\lambda_{availability}\leftarrow\max(score_{availability})$

Function _generate_  _(Given Category, Generate $Rank_{s}core$)_

for  _each tweet $\in$ $tweets_{DataBase}$_ do

if  _$tweet_{category}$ $\in$ category_ then

$\alpha_{1}\leftarrow$ Number of $\alpha_{category}\in tweet$ ;

$\alpha_{2}\leftarrow$ Number of $\beta_{category}\in tweet$ ;

$\alpha_{3}\leftarrow$ Number of $\gamma_{category}\in tweet$ ;

for  _each word $\in$ $(K_{20-category}$ and $H_{5-category})$_ do

$score_{category}$ $\leftarrow$ $score_{category}$ * $\lambda_{category}$;

if  _similarity ({FP or ”quake”}, tweet) ¿ C_ then

$score_{category}$ $\leftarrow$ $score_{category}$ * -1;

end if

end for

$Rank_{score}$ $\leftarrow$ $score_{category}$ ;

end if

return $\big{(}\alpha_{1}+\alpha_{2}+\alpha_{3}\big{)}$ * $Rank_{score}$ ;

end for

end

ALGORITHM 1 Ranking Key Overview

## References

  * (1)
  * Basu et al. (2017) Moumita Basu, Saptarshi Ghosh, Kripabandhu Ghosh, and Monojit Choudhury. 2017.  Overview of the FIRE 2017 track: Information Retrieval from Microblogs during Disasters (IRMiDis). In Working notes of FIRE 2017 - Forum for Information Retrieval Evaluation (CEUR Workshop Proceedings). CEUR-WS.org.
  * Dewan et al. (2016) Prateek Dewan, Varun Bharadhwaj, Aditi Mithal, Anshuman Suri, and Ponnurangam Kumaraguru. 2016\.  Visual Themes and Sentiment on Social Networks To Aid First Responders During Crisis Events.  CoRR abs/1610.07772 (2016).  http://arxiv.org/abs/1610.07772
  * Eriksson and Olsson (2016) Mats Eriksson and Eva-Karin Olsson. 2016.  Facebook and Twitter in Crisis Communication: A Comparative Study of Crisis Communication Professionals and Citizens.  Journal of Contingencies and Crisis Management 24, 4 (2016), 198–208.  https://doi.org/10.1111/1468-5973.12116
  * Fang et al. (2016) Anjie Fang, Craig Macdonald, Iadh Ounis, and Philip Habel. 2016.  Using Word Embedding to Evaluate the Coherence of Topics from Twitter Data. In Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’16). ACM, New York, NY, USA, 1057–1060.  https://doi.org/10.1145/2911451.2914729
  * Gupta et al. (2013) N. Gupta, Abhinav K. R., and Annappa. 2013.  Fuzzy sentiment analysis on microblogs for movie revenue prediction. In 2013 International Conference on Emerging Trends in Communication, Control, Signal Processing and Computing Applications (C2SPCA). 1–4.  https://doi.org/10.1109/C2SPCA.2013.6749350
  * Han Veiga and Eickhoff (2016) Maria Han Veiga and Carsten Eickhoff. 2016.  A Cross-Platform Collection of Social Network Profiles. In Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’16). ACM, New York, NY, USA, 665–668.  https://doi.org/10.1145/2911451.2914666
  * Hürriyetoglu and Oostdijk (2017) Ali Hürriyetoglu and Nelleke Oostdijk. 2017.  Extracting Humanitarian Information from Tweets.. In SMERP@ ECIR. 73–84.
  * Khosla et al. (2017) Prannay Khosla, Moumita Basu, Kripabandhu Ghosh, and Saptarshi Ghosh. 2017.  Microblog Retrieval for Post-Disaster Relief: Applying and Comparing Neural IR Models.  CoRR abs/1707.06112 (2017).  http://arxiv.org/abs/1707.06112
  * Lazer et al. (2009) David Lazer, Alex Pentland, Lada Adamic, Sinan Aral, Albert-László Barabási, Devon Brewer, Nicholas Christakis, Noshir Contractor, James Fowler, Myron Gutmann, Tony Jebara, Gary King, Michael Macy, Deb Roy, and Marshall Van Alstyne. 2009.  Computational Social Science.  Science 323, 5915 (2009), 721–723.  https://doi.org/10.1126/science.1167742 arXiv:http://science.sciencemag.org/content/323/5915/721.full.pdf
  * Le and Mikolov (2014) Quoc V. Le and Tomas Mikolov. 2014.  Distributed Representations of Sentences and Documents.  CoRR abs/1405.4053 (2014).  http://arxiv.org/abs/1405.4053
  * Naaman et al. (2010) Mor Naaman, Jeffrey Boase, and Chih-Hui Lai. 2010\.  Is It Really About Me?: Message Content in Social Awareness Streams. In Proceedings of the 2010 ACM Conference on Computer Supported Cooperative Work (CSCW ’10). ACM, New York, NY, USA, 189–192.  https://doi.org/10.1145/1718918.1718953
  * Nazer et al. (2016) Tahora H. Nazer, Fred Morstatter, Harsh Dani, Huan Liu, undefined, undefined, undefined, and undefined. 2016\.  Finding requests in social media for disaster relief.  2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) 00 (2016), 1410–1413.  https://doi.org/doi.ieeecomputersociety.org/10.1109/ASONAM.2016.7752432
  * Nguyen et al. (2016) Dat Tien Nguyen, Shafiq R. Joty, Muhammad Imran, Hassan Sajjad, and Prasenjit Mitra. 2016.  Applications of Online Deep Learning for Crisis Response Using Social Media Information.  CoRR abs/1610.01030 (2016).  arXiv:1610.01030 http://arxiv.org/abs/1610.01030
  * Purohit et al. (2013) Hemant Purohit, Carlos Castillo, Fernando Diaz, Amit Sheth, and Patrick Meier. 2013.  Emergency-relief coordination on social media: Automatically matching resource requests and offers.  First Monday 19, 1 (2013).  https://doi.org/10.5210/fm.v19i1.4848
  * Rudra et al. (2016) Koustav Rudra, Siddhartha Banerjee, Niloy Ganguly, Pawan Goyal, Muhammad Imran, and Prasenjit Mitra. 2016\.  Summarizing Situational and Topical Information During Crises.  CoRR abs/1610.01561 (2016).  arXiv:1610.01561 http://arxiv.org/abs/1610.01561
  * Rudra et al. (2015) Koustav Rudra, Subham Ghosh, Niloy Ganguly, Pawan Goyal, and Saptarshi Ghosh. 2015.  Extracting Situational Information from Microblogs During Disaster Events: A Classification-Summarization Approach. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM ’15). ACM, New York, NY, USA, 583–592.  https://doi.org/10.1145/2806416.2806485
  * Zhao et al. (2011) Wayne Xin Zhao, Jing Jiang, Jianshu Weng, Jing He, Ee-Peng Lim, Hongfei Yan, and Xiaoming Li. 2011.  Comparing Twitter and Traditional Media Using Topic Models.  Springer Berlin Heidelberg, Berlin, Heidelberg, 338–349.  https://doi.org/10.1007/978-3-642-20161-5_34