# HackCar: a test platform for attacks and defenses on a cost-contained
automotive architecture

Dario Stabili1, Filip Valgimigli2, Edoardo Torrini2 and Mirco Marchetti2
1Dario Stabili is with the Department of Computer Science and Engineering,
Alma Mater Studiorum - University of Bologna<EMAIL_ADDRESS>Valgimigli, Edoardo Torrini and Mirco Marchetti are with the Department of
Engineering “Enzo Ferrari”, University of Modena and Reggio Emilia
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we introduce the design of HackCar, a testing platform for
replicating attacks and defenses on a generic automotive system without
requiring access to a complete vehicle. This platform empowers security
researchers to illustrate the consequences of attacks targeting an automotive
system on a realistic platform, facilitating the development and testing of
security countermeasures against both existing and novel attacks. The HackCar
platform is built upon an $F1-10^{th}$ model, to which various automotive-
grade microcontrollers are connected through automotive communication
protocols. This solution is crafted to be entirely modular, allowing for the
creation of diverse test scenarios. Researchers and practitioners can thus
develop innovative security solutions while adhering to the constraints of
automotive-grade microcontrollers. We showcase our design by comparing it with
a real, licensed, and unmodified vehicle. Additionally, we analyze the
behavior of the HackCar in both an attack-free scenario and a scenario where
an attack on in-vehicle communication is deployed.

##  I Introduction

The integration of microcontrollers into modern automobiles has enabled car
manufacturers to introduce innovative features aimed at enhancing safety and
driving comfort. These functionalities are executed on microcontrollers,
commonly known as Electronic Control Units (ECUs), which interface with the
mechanical components of the vehicle and communicate through various networks.
Among these networks, the most widely adopted one is the Controller Area
Network (CAN), developed by Bosch GmbH in the early 90s [1]. While CAN has
proven effective in ensuring robust communication in the automotive industry,
it lacks essential security assurances crucial for modern applications.

There is a widespread acknowledgment that vehicles are susceptible to
hijacking through the injection of maliciously fabricated messages on the CAN
bus, a vulnerability demonstrated by security researchers through technical
reports and white papers [2, 3]. These attacks exploit the drive-by-wire
capabilities of modern vehicles, allowing control of the driving system
through messages transmitted over the CAN bus. For example, speed control,
activated to maintain a constant vehicle speed for reduced fuel consumption
and emissions, serves as a practical example of a well-known and widely used
_drive-by-wire_ capability. Despite these systems being developed for safety
and comfort, their deployment fundamentals open avenues for targeted attacks,
posing risks to the safety of individuals both inside and outside the vehicle.

With growing concerns about vehicle security, numerous researchers and car
manufacturers are actively engaged in fortifying the CAN network by
implementing diverse security measures, including intrusion detection systems
[4, 5], encryption [6], and authentication [7]. Following the initial public
demonstration of a remote attack on a modern connected vehicle [8],
cybersecurity researchers have proposed various detection algorithms tailored
for in-vehicle communication networks to identify cyber-attacks [4, 9], with a
focus on specific domains.

However, many previous solutions either addressed the problem theoretically or
via a pure software approach, without considering the peculiarities of the
automotive context in their design. While the performance evaluation of
security solutions for in-vehicle networks can be easily demonstrated via a
pure software perspective, proving the vulnerabilities affecting existing
automotive components or protocols requires access to a real vehicle system,
involving investments that might prevent many researchers from undertaking
this crucial research activity.

In this work, we present HackCar, a test platform for attacks and defenses on
a cost-contained automotive architecture. Our platform is designed to be fully
extensible and configurable for every scenario that security researchers want
to address, from in-vehicle network security to V2X communications. We based
the design of HackCar on an $F1-10^{th}$ model stripped of all unnecessary
components, on which we built our computing platform. To prove the
effectiveness of our design, we compared the utilization of the in-vehicle
network deployed on the HackCar test platform and we implemented a forward-
collision avoidance system that, coupled with a simple autonomous driving
algorithm, allows the prototype to stop in case an obstacle is detected by the
forward-facing sensors. Then, we replicated the effects of an attack to the
autonomous driving system, resulting in the platform not stopping in case an
obstacle is detected, thus crashing with it.

The main contribution to the state-of-the-art of HackCar is the public release
of the specifications, designs, and prototype boards required to fully
implement our test system. This allows future researchers to replicate our
prototype, expand on its capabilities, and build a more comprehensive test
platform for attacks and defenses on a secure, safe, and budget-friendly
automotive system.

###  I-A Related Work

Attacks on the automotive systems. The specific challenges posed by the
automotive context in attacking vehicle systems have been extensively
discussed in the literature [10]. One of the most influential works in this
field is presented in [8], where the authors demonstrated a practical approach
to injecting malicious messages into CAN communication, enabling the remote
takeover of a vehicle by bypassing the driver’s commands. Since then, numerous
efforts have been made by security practitioners to introduce novel attacks on
automotive systems [11, 12, 13, 3], although these efforts often require
access to a physical vehicle for result replication.

Defenses for the automotive systems. Immediately following the initial public
demonstrations of attacks on automotive systems, numerous security researchers
began addressing the issue by designing novel detection algorithms for in-
vehicle communication. These algorithms exploit either the physical
characteristics of the microcontrollers [14, 4], the specifications of the CAN
bus protocol [15, 16], or the aggregation of metadata at the network level
[17]. Many of these solutions rely on batch analysis of the content of CAN
communication to scrutinize the data. While this approach is adequate for
showcasing the detection performance of the solution, it falls short of
meeting the specifications of automotive microcontrollers. However, this trend
appears to be on the decline, as many recent works published in the last
couple of years discuss the application of their solutions on different
microcontrollers [5, 9].

Cyber Test platform for automotive. Benchmarking poses one of the significant
challenges for the automotive industry [18]. Many solutions are customized by
individual car manufacturers for their proprietary systems, and portability is
severely limited. From benchmarks for complex systems requiring a dedicated
simulation environment [19, 20, 21, 22, 23, 24] to benchmarks designed for
hardware-in-the-loop scenarios [25, 26, 27, 28, 29], various approaches can be
adopted. However, each approach necessitates a dedicated setup and has limited
applicability. In the realm of benchmarks for anomaly detectors in in-vehicle
communication, researchers have started presenting generic frameworks for
comparing the detection performance of algorithms [30]. They also provide a
targeted analysis of detectors that share the same detection metric [31] and
address this issue from a multidisciplinary perspective [32]. However, these
solutions rely on a simulated environment for testing detection algorithms,
without considering the specific context of the automotive industry or
providing a platform for replicating the consequences of cyber attacks on
automotive systems. In this work, we aim to address all these issues by
presenting a physical prototype for benchmarking both attacks and defenses on
a real automotive system.

###  I-B Outline

The remainder of the paper is organized as follows. Section II outlines the
requirements and the design of HackCar, while Section III presents the
implementation and the components selected for our prototype. Section IV
discusses the validity of the implemented prototype in comparison to a real
vehicle system and demonstrates the consequences of the attack on the test
vehicle. Finally, conclusions and future research directions are addressed in
Section V.

##  II Design of the platform

In this section, we present the requirements (II-A) and the design (II-B) of
the _HackCar_ test platform. Specifically, we will discuss the design of the
three main components of the test platform: (I) the sensing system, (II) the
on-board controller, and (III) the in-vehicle network. Although each of these
components is discussed as a single entity in our design, during the
implementation process, we emphasize that a single component can be composed
of multiple elements without impacting the previously made design choices.

###  II-A Requirements of the platform

To define the requirements of the test platform, it is necessary to first
outline the operational scenarios that we aim to support. Given that the
primary objective of this work is to present a platform for analyzing the
consequences of cyber-attacks on the system under various circumstances, the
initial scenario we define supports self-driving capabilities. It has the
ability to move along a pre-defined route without requiring an external
controller, featuring an enabled Automatic Emergency Braking (AEB) system,
thereby replicating the functionalities of a _level 3+_ Advanced Driver
Assistance System (ADAS). Building upon this operational scenario, the second
one is defined by disabling self-driving capabilities and introducing an
external controller to command the platform. In this second scenario, the same
AEB system is deployed as in the first scenario, providing basic _level 1_
ADAS capabilities.

In summary, the two operational scenarios supported by the HackCar platform
are:

  1. 1.

ManualAEB, where the platform is manually controlled by a remote controller,
and an Automatic Emergency Braking (AEB) system is enabled to replicate a
_level 1_ ADAS.

  2. 2.

AutoDrive, where the platform can move along a pre-defined route without
requiring any external controller and with the AEB system enabled, replicating
the functionality of a _level 3+_ ADAS.

To support these two operational scenarios, the requirements of the test
platform (assuming that the actuators to replicate the behavior of a vehicle
by accelerating, steering, and braking are supported) can be summarized as
follows:

  * •

Wireless interface for the remote controller;

  * •

Sensing system for forward-object detection;

  * •

On-board controller to operate on the braking system (for both scenarios) and
the accelerating system (in the _AutoDrive_ scenario);

  * •

On-board controller with the ability to switch between the two operational
modes.

Additionally, we include two dedicated microcontrollers to support different
attacks and defense solutions at n-vehicle network level. Despite these
microcontrollers enable researchers to deploy attacks and defense solutions to
the _HackCar_ platform, we emphasize that this paper does not focus on
discussing novel attack scenarios or novel detection techniques. The inclusion
of support for both attacks and defense mechanisms in the design process of
the test platform is representative of its capabilities for demonstrating
attack consequences and testing security solutions in the automotive context
without requiring a full-size vehicle.

###  II-B Design of the platform

The _HackCar_ test platform is constructed with three main components (the
_sensing system_ , the _on-board controllers_ and the _in-vehicle network_),
each responsible for distinct functions to replicate the operational scenarios
supported by the platform. A high-level representation of the design of the
_HackCar_ test platform is shown in Figure 1.

Figure 1: High-level overview of the _HackCar_ test platform

_Sensing system design._ To facilitate the development of operational
scenarios, we require a sensing system that supports at least _level 3_ self-
driving capabilities, with a primary emphasis on the obstacle detection
system. Despite defining both _ManualAEB_ and _AutoDrive_ operational
scenarios as representative of two different ADAS levels, it is noteworthy
that the only sensing system required for both scenarios is the obstacle
detection system. The forward obstacle detection feature of _HackCar_ can be
implemented using either a LiDAR-based solution or stereo cameras directed
towards the front of the test platform.

_On-board controller._ The on-board controller serves as the computational
core of our system, analyzing data generated by the sensing system to detect
obstacles, halt the prototype, and prevent collisions. Consequently, the on-
board controller is tasked with managing the actuators that control the
platform’s dynamics, including the braking system (for both operational
scenarios) and the accelerating and steering systems (only for the _AutoDrive_
scenario). Additionally, the on-board controller must provide a wireless
interface for the remote controller, allowing input in the _ManualAEB_
scenario.

Given the diverse features required at the controller level, it is advisable
to design the test platform with a multi-controller approach instead of opting
for a single-board controller. In our final design, we have incorporated four
different controllers:

  * •

Sensing system controller (SSC): Responsible for evaluating the presence of an
obstacle in the proximity of the vehicle by analyzing data generated from the
sensing system.

  * •

Main controller unit (MCU): Responsible for accessing the actuators of the
test platform and managing the two operational scenarios. Specifically, when a
specific operational scenario is selected, the main controller is responsible
for implementing all the required functions. In our prototype, the main
controller provides the wireless interface used to connect the remote
controller to the platform (in the _ManualAEB_ scenario). It is also
responsible for implementing the self-driving capabilities required by the
_AutoDrive_ scenario.

  * •

Attack controller (Attacker): Responsible for replicating attacks on the
vehicle to study the consequences of each attack scenario in different
operational scenarios.

  * •

Detection controller (Detector): Responsible for detecting anomalies in the
prototype’s behavior by analyzing various types of data according to the
tested detection algorithm.

_In-Vehicle Networks._ To facilitate communication among the controllers that
constitute the computational platform of our test prototype, we designed them
to communicate with each other through an in-vehicle network, replicating the
behavior of a full-sized vehicle. Therefore, the obvious choice in designing
the in-vehicle network communication was to rely on the Controller Area
Network (CAN), as it is the most widely deployed communication network for in-
vehicle applications. The CAN is an industrial bus standard designed to
facilitate data exchange between devices without requiring a host computer. It
is widely adopted in the automotive context due to its high resilience to
electromagnetic interference and cost-effectiveness. Data on the CAN bus is
exchanged by microcontrollers via _data frames_ , a specific type of message
defined in the CAN standard. The two most crucial fields of the data frame are
the _ID_ (used to identify the type of message) and the _DATA_ (a sequence of
up to $64$ bits containing various values). Each data frame with a particular
ID value is sent by one and only one microcontroller, while its content can be
used by many microcontrollers for their functioning. As the CAN standard does
not define how signals are encoded in the data field, it is necessary to
define the number, structure, encoding, and semantics of the encoded signals.

##  III Implementation of the platform

In this section, we discuss the architectural decisions made during the
implementation of the three core components of our platform. The whole
implementation process is based on a Traxxas Ford Fiesta ST Rally [33] model
as the foundational platform for developing the sensing, controller, and
communication systems. The chosen platform is a scaled-down replica,
maintaining a $1:10$ ratio compared to the original Ford Fiesta ST Rally
vehicle. This model is equipped with all the necessary actuators to access
braking, accelerating, and steering functions.

_Sensing system._ The sensing system is built around a Hokuyo $UST-10LX$ $2D$
LiDAR [34]. This LiDAR is widely utilized for implementing detection and
localization in autonomous mobile robots, automated guided vehicles, and
carts. Equipped with an Ethernet interface, it offers a $270\degree$ field-of-
view up to a distance of $10$ meters. With $1081$ measurement steps, it
achieves an angular resolution of $0.25\degree$ and boasts a rapid response
time of $25ms$, making it one of the most reliable components for object
detection.

_On-Board Controllers._ The on-board controllers are implemented on different
microcontrollers to replicate the heterogeneity of a typical in-vehicle
electrical and electronic architecture. The details are presented as follows:

  * •

Sensing system controller (SSC). The SSC is implemented on a NVIDIA Jetson
Nano board [35], a single-board computer designed for low-power environments
and equipped with Robot Operating System (ROS) 2 [36]. Initially developed for
robotic systems, ROS2’s high versatility led to its application in real-time
systems as well. It is important to note that the SSC is configured to provide
only basic self-driving and object detection capabilities, although the
current hardware version of _HackCar_ can support more advanced and full self-
driving capabilities.

  * •

Main controller unit (MCU). The MCU is implemented on an Infineon Aurix
TriCore $TC297$ [37] microcontroller, an integrated and advanced automotive-
grade microcontroller widely adopted in the automotive industry. The Aurix
TriCore controller is connected to the actuators of the Traxxas model to
control braking, acceleration, and steering via a Trampa VESC $6MKVI$
Electronic Speed Controller (ESC) [38]. The VESC ESC allows us to control all
the systems responsible for managing the platform’s dynamics via a single
interface, thereby reducing the complexity of the different sub-systems.

  * •

Attack controller. The attack controller is implemented on a CANPico board
[39], equipped with an $MPC2517FD$ CAN controller and a CAN transceiver to
provide access to the CAN bus. The CANPico is shipped with a source SDK for
Micropython, supporting the CANHack toolkit API [40] for low-level attacks on
the CAN bus.

  * •

Detection controller. The detection controller is based on another Infineon
Aurix TriCore $TC297$ controller. We emphasize that the performance evaluation
of various anomaly detectors for CAN networks is beyond the scope of this
work. However, we chose to implement a detection controller on the Aurix
TriCore board due to the interfaces available on the board, making it a valid
choice for designing and testing solutions that go beyond the only CAN bus.

_In-vehicle CAN._ In-vehicle communication relies on CAN messages transmitted
every $10ms$ from various controllers. Since the CAN protocol allows car
manufacturers to define the content and encoding of signals on the CAN bus, we
implemented our network based on these messages

  * •

RPM [ID: 0x400, DLC: 4 Bytes]: This message contains the target RPMs of the
engine in the AutoDrive operational scenario. The sensing system controller
generates this message, while the main controller uses it to set the RPMs of
the engine via the VESC controller.

  * •

STEERING [ID: 0x401, DLC: 4 Bytes]: This message holds the target radial value
of the steering wheel required in both the ManualAEB (converted from user
input) and AutoDrive scenarios. The sensing system controller generates this
message, and the main controller uses it to set the angle of the steering
wheel via the VESC controller.

  * •

BREAK [ID: 0x402, DLC: 1 Byte]: This message contains the target value of the
braking system required for the Automatic Emergency Brake feature. The sensing
system controller generates this message, and the main controller uses it to
decrease the value of the RPM of the engine via the VESC controller.

In addition to these messages, we implemented three service messages to switch
between the two operational scenarios (CAN ID 0x500), activate and deactivate
the AEB (CAN ID 0x501), and trigger the execution of attacks on the Attack
controller (CAN ID 0x502). These messages are defined with a DLC of $1$ Byte
and are only sent on the network when required by the user.

##  IV Experimental evaluation

In this section, we present the experimental evaluation of the HackCar test
platform. Before presenting the results of the evaluation, we introduce the
attacks currently supported by the platform in Section IV-A, while both
validation and functional evaluation are discussed in Section IV-B.

###  IV-A Threat model

The threat model supported in the prototype version of HackCar is based on the
most effective type of attacks for in-vehicle communication, namely the
_message injection_ attack. Specifically, we consider an attacker with access
to the in-vehicle network through either the On-Board Diagnostic interfaces,
an additional device maliciously installed on the vehicle, or by compromising
an ECU [8]. We do not consider the scenario where the attacker is able to
compromise an existing ECU to modify its normal behavior.

In our experimental evaluation, we assume the attacker can subvert the normal
behavior of the AEB system deployed on the _sensing system controller_. For
this purpose, the attacker controller is configured to intercept the RPM
message on the CAN, preventing the main controller from stopping the platform.
To replicate a stealthy behavior, the attacker controller is configured to
send the message _after_ the one generated by the _sensing system controller_
is sent on the network, effectively overwriting it.

###  IV-B Validation and Functional evaluation

For the experimental evaluation of the _HackCar_ test platform, we focus on
the experimental validation of the platform concerning the in-vehicle network
of an unmodified, licensed vehicle and the functional evaluation of the
platform against the attack discussed in the threat model. We emphasize that,
despite _HackCar_ offering support for a defense system, this work does not
focus on the detection capabilities since it would only require the
implementation of existing IDS for CAN communication [41, 9, 31], thus not
providing any substantial contribution to the state-of-the-art in this
particular field.

HackCar Validation. The validation of the HackCar test platform is based on
the analysis of CAN bus utilization concerning the in-vehicle data collected
from an unmodified, licensed vehicle. The objective of this test is to compare
our implementation with the most frequently messages in our reference CAN
data, as these are likely to be messages carrying sensor readings related to
the _drive-by-wire_ features of our reference vehicle.

Functional Evaluation. In the functional validation of the HackCar test
platform, we focus on analyzing the content of CAN messages under attack to
scrutinize the behavior of the test platform while replicating the attack
described in the previous section. The aim of this test is to demonstrate
that, under attack conditions, the consequences of the attack can also be
observed at the CAN communication level.

###  IV-C Results analysis

HackCar Validation Results. The results of the validation tests are presented
in Figure 2, where the CAN bus utilization of the test platform is compared
with data collected from an unmodified, licensed vehicle.

Figure 2: Validation of the HackCar test platform against a real vehicle

Figure 2 compares the CAN bus utilization (represented on the $y$-axis) of the
HackCar test platform (red line) with the most frequent messages (sent with a
frequency of $100$ Hz) of our reference vehicle (blue line) over a duration of
$60$ seconds of CAN data. The results presented in Figure 2 indicate that both
platforms exhibit similar behavior, with the HackCar test platform reaching
approximately the same utilization percentage as the reference vehicle. We
emphasize that these results serve as a simple yet effective demonstration
that the implemented architecture can be configured to behave similarly to a
specific subset of real vehicle CAN messages responsible for the same
functions.

Functional evaluation results. The results of the functional evaluation test
are presented in Figure 3, where the rotational speed of the engine is
compared with the target speed set by the controller.

Figure 3: Functional evaluation of the HackCar test platform in a normal
operating scenario (top plot) and under attack (bottom plot)

Figure 3 illustrates the behavior of the HackCar test platform in both an
attack-free (top plot) and under-attack (bottom plot) scenarios. In both
scenarios, the target rotation per minute (RPMs) set by the MCU are depicted
in blue, while the actual RPMs of the HackCar platform, as observed from the
electric engine, are represented by the green dashed line. The yellow cross-
hatched area in both plots indicates the presence of an obstacle in front of
the HackCar, while the red vertical lines in the bottom plot denote the start
and end of the attack.

In both plots, the obstacle is detected approximately $0.5$ meters in front of
the vehicle after around $30$ seconds, with the attack triggered $5$ seconds
before the detection of the obstacle in the second scenario. Analyzing the
results presented in Figure 3, it is evident that there is an initial
oscillation in the real RPMs due to the action of the HackCar platform
controller, resulting in reaching the target speed of $6000$ RPMs a few
seconds after the start of the HackCar. The speed is then maintained around
the equilibrium point ($6000$ RPMs) until the obstacle is detected.

In the scenario depicted in the top part of Figure 3, the detection of the
obstacle in front of the HackCar results in the MCU setting the target speed
to $0$ RPMs, forcing the vehicle to stop in under a second. On the other hand,
in the second scenario, the actual RPMs of the electric engine are maintained
around the equilibrium point by the controller because the attack is triggered
before the detection of the obstacle. In this latter scenario, it is also
noticeable that the actual RPMs are not as stable as before the obstacle
detection, owing to the attack targeting the controller. The attack introduces
sensible oscillations in the system since, apart from receiving malicious
messages containing the target speed of $6000$ RPMs, the controller also
receives legitimate messages from the MCU containing the target speed of $0$
RPMs. This behavior, as already showcased in [42], is a realistic
representation of the normal operation of an engine controller.

##  V Conclusion

In this paper, we presented the design of HackCar, a test platform for attacks
and defenses on a generic and configurable automotive system. We supported our
design with a real implementation based on an _F1- $10^{th}$_ platform,
equipped with at least $4$ different automotive-grade microcontrollers. These
microcontrollers are responsible for managing the sensing system of the
platform, enabling the implementation of various ADAS features. The main
controller governs the target speed and heading of the vehicle while operating
in autonomous mode. The platform also includes a malicious attacker with
access to in-vehicle communication, providing researchers the ability to
prototype novel attacks on a small scale or replicate known cyberattacks to
study their consequences in a realistic automotive environment. Additionally,
a detection system is incorporated, enabling researchers to develop and test
architectural solutions to existing or novel cyberattacks on the vehicle
system.

The results of the validation and functional behavior tests demonstrate that
our platform behaves similarly to an unmodified licensed vehicle. The system
can be easily utilized by security researchers to showcase the consequences of
cyberattacks on an automotive system without requiring access to a full
vehicle.

## Acknowledgments

This work was partially supported by projects SERICS (PE00000014) under the
MUR National Recovery and Resilience Plan funded by the European Union -
NextGenerationEU and FuSeCar funded by the MIUR Progetti di Ricerca di
Rilevante Interesse Nazionale (PRIN) Bando 2022 - grant 2022W3EPEP.

## References

  * [1] Bosch. (1991) Can specification version 2.0.
  * [2] C. Miller and C. Valasek. (2014) Adventures in automotive networks and control units.
  * [3] Keen Security Lab of Tencent. (2016) Car hacking research: Remote attack tesla motors. [Online]. Available: http://keenlab.tencent.com/en/2016/09/19/Keen-Security-Lab-of-Tencent-Car-Hacking-Research-Remote-Attack-to-Tesla-Cars/
  * [4] M. Kneib and C. Huth, “Scission: Signal characteristic-based sender identification and intrusion detection in automotive networks,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’18. New York, NY, USA: ACM, 2018, pp. 787–800. [Online]. Available: http://doi.acm.org/10.1145/3243734.3243751
  * [5] D. Stabili, L. Ferretti, M. Andreolini, and M. Marchetti, “Daga: Detecting attacks to in-vehicle networks via n-gram analysis,” _IEEE Transactions on Vehicular Technology_ , vol. 10, p. 15, 2022.
  * [6] B. Groza, S. Murvay, A. van Herrewege, and I. Verbauwhede, “Libra-can: A lightweight broadcast authentication protocol for controller area networks,” in _Cryptology and Network Security_ , J. Pieprzyk, A.-R. Sadeghi, and M. Manulis, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 185–200.
  * [7] R. Kurachi, Y. Matsubara, H. Takada, H. Ueda, and S. Horihata, “Cacan: Centralized authentication system in can (controller area network),” 2016.
  * [8] C. Miller and C. Valasek. (2015) Remote exploitation of an unaltered passenger vehicle. White paper of Blackhat US conference. [Online]. Available: http://illmatics.com/Remote%20Car%20Hacking.pdf
  * [9] S. Longari, C. A. Pozzoli, A. Nichelini, M. Carminati, and S. Zanero, “Candito: Improving payload-based detection of attacks on controller area networks,” in _Cyber Security, Cryptology, and Machine Learning_ , S. Dolev, E. Gudes, and P. Paillier, Eds. Cham: Springer Nature Switzerland, 2023, pp. 135–150.
  * [10] S. Checkoway, D. McCoy, B. Kantor, D. Anderson, H. Shacham, S. Savage, K. Koscher, A. Czeskis, F. Roesner, and T. Kohno, “Comprehensive experimental analyses of automotive attack surfaces,” in _Proceedings of the 20th USENIX Conference on Security_ , ser. SEC’11. Berkeley, CA, USA: USENIX Association, 2011, pp. 6–6. [Online]. Available: http://dl.acm.org/citation.cfm?id=2028067.2028073
  * [11] H. Lee, K. Choi, K. Chung, J. Kim, and K. Yim, “Fuzzing CAN packets into automobiles,” in _2015 IEEE 29th Int’l Conf. on Advanced Information Networking and Applications_ , March 2015.
  * [12] K.-T. Cho and K. G. Shin, “Error handling of in-vehicle networks makes them vulnerable,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’16. New York, NY, USA: ACM, 2016, pp. 1044–1055. [Online]. Available: http://doi.acm.org/10.1145/2976749.2978302
  * [13] A. Palanca, E. Evenchick, F. Maggi, and S. Zanero, “A stealth, selective, link-layer denial-of-service attack against automotive networks,” in _Detection of Intrusions and Malware, and Vulnerability Assessment - 14th International Conference, DIMVA 2017, Bonn, Germany, July 6-7, 2017, Proceedings_ , 2017, pp. 185–206. [Online]. Available: https://doi.org/10.1007/978-3-319-60876-1_9
  * [14] K. Cho and K. G. Shin, “Viden: Attacker identification on in-vehicle networks,” _CoRR_ , vol. abs/1708.08414, 2017. [Online]. Available: http://arxiv.org/abs/1708.08414
  * [15] M. Gmiden, M. H. Gmiden, and H. Trabelsi, “An intrusion detection method for securing in-vehicle CAN bus,” in _Int’l Conf. Sciences and Techniques of Automatic Control and Computer Engineering_ , 2016.
  * [16] D. Stabili and M. Marchetti, “Detection of missing CAN messages through inter-arrival time analysis,” in _2019 IEEE 90th Vehicular Technology Conf._ , Sep. 2019.
  * [17] N. Nowdehi, W. Aoudi, M. Almgren, and T. Olovsson, “CASAD: CAN-aware stealthy-attack detection for in-vehicle networks,” 2019.
  * [18] S. Kramer, D. Ziegenbein, and A. Hamann, “Real world automotive benchmarks for free,” in _6th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS)_ , vol. 130, 2015.
  * [19] H. Elmqvist, S. E. Mattsson, H. Olsson, J. Andreasson, M. Otter, C. Schweiger, and D. Brück, “Real-time simulation of detailed automotive models,” in _Proceedings_ , 2003, pp. 29–38.
  * [20] T. Buranathiti and J. Cao, “Benchmark simulation results: automotive underbody cross member (benchmark 2),” in _AIP Conference Proceedings_ , vol. 778, no. 1. American Institute of Physics, 2005, pp. 1004–1112.
  * [21] K. Gangel, Z. Hamar, A. Háry, Á. Horváth, G. Jandó, B. Könyves, D. Panker, K. Pintér, M. Pataki, M. Szalai _et al._ , “Modelling the zalazone proving ground: a benchmark of state-of-the-art automotive simulators prescan, ipg carmaker, and vtd vires,” _Acta Technica Jaurinensis_ , vol. 14, no. 4, pp. 488–507, 2021.
  * [22] I. Paranjape, A. Jawad, Y. Xu, A. Song, and J. Whitehead, “A modular architecture for procedural generation of towns, intersections and scenarios for testing autonomous vehicles,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_ , 2020, pp. 162–168.
  * [23] A. Wallace, S. Khastgir, X. Zhang, S. Brewerton, B. Anctil, P. Burns, D. Charlebois, and P. Jennings, “Validating simulation environments for automated driving systems using 3d object comparison metric,” in _2022 IEEE Intelligent Vehicles Symposium (IV)_ , 2022, pp. 860–866.
  * [24] Z. Qiao, X. Sun, H. Loeb, and R. Mangharam, “Drive right: Shaping public’s trust, understanding, and preference towards autonomous vehicles using a virtual reality driving simulator,” in _2023 IEEE Intelligent Vehicles Symposium (IV)_ , 2023, pp. 1–8.
  * [25] B. Ellies, C. Schenk, and P. Dekraker, “Benchmarking and hardware-in-the-loop operation of a 2014 mazda skyactiv 2.0 l 13: 1 compression ratio engine,” SAE Technical Paper, Tech. Rep., 2016.
  * [26] Y. Shao, M. A. M. Zulkefli, Z. Sun, and P. Huang, “Evaluating connected and autonomous vehicles using a hardware-in-the-loop testbed and a living lab,” _Transportation Research Part C: Emerging Technologies_ , vol. 102, pp. 121–135, 2019.
  * [27] M. Abboush, D. Bamal, C. Knieke, and A. Rausch, “Hardware-in-the-loop-based real-time fault injection framework for dynamic behavior analysis of automotive software systems,” _Sensors_ , vol. 22, no. 4, p. 1360, 2022.
  * [28] M. Pechinger, G. Schröer, K. Bogenberger, and C. Markgraf, “Hardware in the loop test using infrastructure based emergency trajectories for connected automated driving,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_ , 2020, pp. 357–362.
  * [29] P. Scheffe and B. Alrifaee, “A scaled experiment platform to study interactions between humans and cavs,” in _2023 IEEE Intelligent Vehicles Symposium (IV)_ , 2023, pp. 1–6.
  * [30] D. Stabili, F. Pollicino, and A. Rota, “A benchmark framework for can ids,” in _Italian Conference on Cybersecurity 2021 (ITASEC)_ , April 2021, pp. 233–245.
  * [31] F. Pollicino, D. Stabili, and M. Marchetti, “Performance comparison of timing-based anomaly detectors for controller area network: A reproducible study,” _ACM Trans. Cyber-Phys. Syst._ , jun 2023, just Accepted. [Online]. Available: https://doi.org/10.1145/3604913
  * [32] D. Stabili, R. Romagnoli, M. Marchetti, B. Sinopoli, and M. Colajanni, “A multidisciplinary detection system for cyber attacks on powertrain cyber physical systems,” _Future Generation Computer Systems_ , vol. 144, pp. 151–164, 2023. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167739X23000602
  * [33] Traxxas. (2024) Ford Fiesta ST Rally 1:10 model. [Online]. Available: https://traxxas.com/products/models/electric/ford-fiesta-st-rally
  * [34] Hokuyo Automatic USA Corporation. (2024) UST-10LX. [Online]. Available: https://hokuyo-usa.com/products/lidar-obstacle-detection/ust-10lx
  * [35] NVIDIA. (2024) Jetson Nano Developer Kit. [Online]. Available: https://developer.nvidia.com/embedded/jetson-nano-developer-kit
  * [36] Open Robotics. (2024) Robot Operating System v2. [Online]. Available: https://github.com/ros2
  * [37] Infineon. (2024) AURIX Family - TC297TA. [Online]. Available: https://www.infineon.com/cms/en/product/microcontroller/32-bit-tricore-microcontroller/32-bit-tricore-aurix-tc2xx/aurix-family-tc297ta-adas/
  * [38] TRAMPA Boards. (2024) VESC 6 MkVI. [Online]. Available: https://trampaboards.com/vesc-6-mkvi--the-amazing-trampa-vesc-6-mkvi--gives-maximum-power-original-p-27536.html
  * [39] CANIS Automotive Labs. (2024) CANPico. [Online]. Available: https://canislabs.com/canpico/
  * [40] ——. (2024) CANHack. [Online]. Available: https://github.com/kentindell/canhack
  * [41] M. Marchetti and D. Stabili, “Anomaly detection of CAN bus messages through analysis of ID sequences,” in _IEEE Proc. Intelligent Vehicles Symp._ , June 2017.
  * [42] D. Stabili, R. Romagnoli, M. Marchetti, B. Sinopoli, and M. Colajanni, “Exploring the consequences of cyber attacks on powertrain cyber physical systems,” 2022.


# From geometry to generating functions:
rectangulations and permutations

Andrei Asinowski1 Supported by FWF — Austrian Science Fund, Grant P32731.
Cyril Banderier2  1Institut für Mathematik, Universität Klagenfurt, Austria.
https://me.aau.at/~anasinowski
2LIPN, CNRS & Université Sorbonne Paris Nord, France.
https://lipn.fr/~banderier

14 November 2023

(14 November 2023)

###### Abstract

We enumerate several classes of pattern-avoiding rectangulations. We establish
bijective links with pattern-avoiding permutations, prove that their
generating functions are algebraic, and confirm several conjectures by Merino
and Mütze. We also analyze a new class of rectangulations, called whirls,
using a generating tree.

###### keywords:

Rectangulations, permutations, pattern avoidance, generating functions

##  1 Introduction

A rectangulation of size $n$ is a tiling of a rectangle by $n$ rectangles such
that no four rectangles meet in a point. In the literature, rectangulations
are also called floorplans or rectangular dissections.

Such structures appear naturally for architectural building plans, integrated
circuits (see Figure 1), and were investigated since the 70s with some graph
theory, computational geometry, and combinatorial optimization point of views
[17, 19]. Then, in the 2000s, rectangulations began to be investigated with
more combinatorial approaches [1, 2, 4, 13, 18]:it was shown that some
important families of rectangulations are enumerated by famous integer
sequences (e.g., Baxter, Schröder, Catalan numbers) and that they have strong
links with pattern-avoiding permutations (as studied in the seminal article
[12]).

Figure 1: a) VLSI are rectangulations playing an important role for integrated
circuits.
b) The artwork Composition décentralisée, 1924, by Theo van Doesburg
(1883–1931).
c) A book on the geometry of building plans [19]. Its cover is not a
rectangulation according to our definition (as it contains instances of 4
rectangles meeting in a point).
d) This solution to Tutte’s famous "Squaring the square" is a rectangulation.

##  2 Patterns in rectangulations and summary of our results

Two rectangulations are isomorphic if one can push (horizontally or
vertically) some of their segments (without meeting an extremity of any other
segment) so that they become identical. This leads to a natural notion of
pattern containment. E.g., in the following rectangulations, we highlight an
occurrence of  (in green),  (in blue),  (in red).

Note that amongst these three rectangulations, only the first two are
isomorphic.

We are interested in the enumeration of different natural classes of
rectangulations, where the goal is to count the number of non-isomorphic
rectangulations of size $n$.E.g.,  -avoiding rectangulations are enumerated by
Baxter numbers [1, 12].

Recently, Arturo Merino and Torsten Mütze tackled the question of the
exhaustive generation of rectangulations avoiding any subset of $\\{\\!$
$\\!,$ $\\!,$ $\\!,$ $\\!,$ $\\!,$ $\\!,$ $\\!,$ $\\!\\}.$In [16], they
present an efficient algorithm to generate such rectangulations111Let us here
advertise the section dedicated to rectangulations in the nice Combinatorial
Object Server, created by Frank Ruskey, and now handled by Torsten Mütze, Joe
Sawada, and Aaron Williams.. This led to a surprising observation: many
sequences coincide (at least up to size $12$) with integer sequences which
already appeared in the literature, for apparently unrelated problems.

In Section 3, we solve all the cases related to rectangulations that avoid  .
These are guillotine diagonal rectangulations, and they correspond to
separable permutations (i.e. $2413,3142)$-avoiding permutations). When they
avoid further patterns, we prove the following table (where we use the notion
of vincular patterns in permutations, see Bóna’s overview [7]), and in Theorem
1 we provide generating functions for all these cases.

| Entry in
---
[16, Table 3]
| Guillotine diagonal
---
rectangulations avoiding…
| Separable permu-
---
tations avoiding…
G.f. | OEIS
1234 | $\emptyset$ | $\emptyset$ | alg. | A006318
12345 |  | $2\underline{14}3$ | alg. | A106228
12347 |  | $21354$ | alg. | A363809
123456 |  | $2\underline{14}3,3\underline{41}2$ | alg. | A078482
123457 |  | $2143$ | alg. | A033321
123458 |  | $2\underline{14}3,45312$ | alg. | A363810
123478 |  | $21354,45312$ | rat. | A363811
1234567 |  | $2143,3\underline{41}2$ | alg. | A363812
1234578 |  | $2143,45312$ | rat. | A363813
12345678 |  | $2143,3412$ | rat. | A006012

In Section 4, we additionally prove algebraicity of some non-guillotine
models, such as vortex rectangulations (A026029, case 1345678 in [16]) and
whirls (A002057).

##  3 Guillotine diagonal rectangulations

The patterns $P_{1}=$ , $P_{2}=$ , $P_{3}=$ , $P_{4}=$ were considered in some
earlier work (for example [1, 10]) since they characterize some special kinds
of rectangulations.

A rectangulation $\mathcal{R}$ is guillotine if it is of size $1$, or if it
has a cut (a segment whose endpoints lie on opposite sides of $R$) that splits
it into two guillotine rectangulations. It is well known [1] that a
rectangulation is guillotine if and only if it avoids $P_{1}=$ and $P_{2}=$
(these two patterns are called windmills).

A rectangulation $\mathcal{R}$ is called diagonal if it avoids
$P_{3}=\leavevmode\hbox to15.51pt{\vbox
to15.51pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{7.25558pt}{0.0pt}\pgfsys@lineto{7.25558pt}{14.51118pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{4.35333pt}\pgfsys@lineto{7.25558pt}{4.35333pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{7.25558pt}{10.15784pt}\pgfsys@lineto{14.51118pt}{10.15784pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ and
$P_{4}=\leavevmode\hbox to15.51pt{\vbox
to15.51pt{\pgfpicture\makeatletter\hbox{\hskip 0.5pt\lower-0.5pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{7.25558pt}\pgfsys@lineto{14.51118pt}{7.25558pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{10.15784pt}{7.25558pt}\pgfsys@lineto{10.15784pt}{14.51118pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{1.0pt}\pgfsys@invoke{
}{}\pgfsys@moveto{4.35333pt}{0.0pt}\pgfsys@lineto{4.35333pt}{7.25558pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$. This notion is due
to the fact that such a rectangulation can be drawn so that the NW–SE diagonal
of $R$ intersects all the rectangles. At the same time, diagonal
rectangulations are frequently seen as canonical representatives of
rectangulations up to the “weak equivalence” [3, 10].

These two classes have — in different ways — stronger structural properties
than the general case. Therefore we expected that families that avoid these
four patterns and any other subset of patterns of $\\{$ , , , $\\}$ will yield
noteworthy results. There are essentially ten different such models, all
listed in [16, Table 3]. Amongst these 10 cases, 3 of them can be solved by
ad-hoc bijections with trees (see [2, 4]), 2 are conjectured by Merino and
Mütze to lead to algebraic generating functions, and for the remaining 5 no
conjectures were provided. Below we present a unified framework which allows
us to solve these 10 cases (confirming en passant the conjectures of Merino
and Mütze). The main result of this section is Theorem 1, which, in
particular, states that all these cases are in fact algebraic!

######  Theorem 1.

The generating functions for the ten guillotine cases are algebraic.

  1. 1.

The generating function of rectangulations avoiding  is

$F(t)=\frac{1-t-\sqrt{1-6t+t^{2}}}{2}.$

  2. 2.

The generating function of rectangulations avoiding  satisfies

$tF^{3}+2tF^{2}+(2t-1)F+t=0.$

  3. 3.

The generating function of rectangulations avoiding  ) satisfies
$t^{4}(t-2)^{2}F^{4}+t(t-2)(4t^{3}-7t^{2}+6t-1)F^{3}+(2t^{4}-t^{3}-2t^{2}+5t-1)F^{2}-(4t^{3}-7t^{2}+6t-1)F+t^{2}=0$.

  4. 4.

The generating function of rectangulations avoiding  is

$F(t)=\frac{1-3t+t^{2}-\sqrt{1-6t+7t^{2}-2t^{3}+t^{4}}}{2t}.$

  5. 5.

The generating function of rectangulations avoiding  is

$F(t)=\frac{(1-t)(1-2t)-\sqrt{(1-t)(1-5t)}}{2t(2-t)}.$

  6. 6.

The generating function of rectangulations avoiding  satisfies
$t^{8}(t-2)^{2}F^{4}-t^{3}(t^{2}-3t+2)(t^{5}-7t^{4}+4t^{3}-6t^{2}+5t-1)F^{3}-t(t-1)(4t^{7}-22t^{6}+37t^{5}-42t^{4}+53t^{3}-35t^{2}+10t-1)F^{2}$
$-(5t^{6}-16t^{5}+15t^{4}-28t^{3}+23t^{2}-8t+1)(t-1)^{2}F-(2t^{5}-5t^{4}+4t^{3}-10t^{2}+6t-1)(t-1)^{2}=0$.

  7. 7.

The generating function of rectangulations avoiding  is

$F(t)=\frac{t(1-16t+11t^{2}-434t^{3}+1045t^{4}-1590t^{5}+1508t^{6}-846t^{7}+252t^{8}-30t^{9})}{(1-2t)^{4}(1-3t+t^{2})^{2}(1-4t+2t^{2})}.$

  8. 8.

The generating function of rectangulations avoiding  is

$F(t)=\frac{1-3t-t^{2}+2t^{3}-\sqrt{1-6t+7t^{2}+2t^{3}+t^{4}}}{2t^{2}(2-t)}.$

  9. 9.

The generating function of rectangulations avoiding  is

$F(t)=\frac{t(1-t)(1-7t+16t^{2}-11t^{3}+2t^{4})}{(1-4t+2t^{2})(1-3t+t^{2})^{2}}.$

  10. 10.

The generating function of rectangulations avoiding  is

$F(t)=\frac{t(1-2t)}{1-4t+2t^{2}}.$

We now present separable permutations — a fundamental class which will be used
in the proof of this theorem.

###  3.1 Rectangulations avoiding  , and separable permutations

A permutation $\pi$ is separable if it is either of size $1$, or if it is
(recursively) a direct sum of separable permutations (in this case $\pi$ is
called ascending separable) or a skew sum of separable permutations (in this
case $\pi$ is called descending separable). We refer to [7] for these notions.
Accordingly, separable permutations are precisely the non-empty
$(2413,3142)$-avoiding permutations [8].

The first key step in the proof of Theorem 1 is “translating” (sets of)
geometric patterns into (sets of) permutation patterns. In all 10 cases we
obtain a bijection between a subclass of guillotine rectangulations and a
subclass of separable permutations. We provide details for the first three
cases, and just give the key decompositions for the other cases.

Case $1$: Guillotine diagonal rectangulations. They are in bijection with
separable permutations (see, e.g., [1, 4]). Here is a natural recursive
bijection: the rectangulation of size 1 is mapped to the permutation of size
1, and the recursive steps are illustrated in the following drawing. The left
and the middle illustrations describe the transformation for horizontal and
vertical cuts, and the right illustration is an example of size 11.

The recursive definition of separable permutations translates directly to a
system of equations that binds $A(t)$, $D(t)$, and $F(t)=t+A(t)+D(t)$, the
generating functionsfor ascending, descending, and all separable permutations.
Since an ascending (resp. descending) separable permutation can be seen as a
sequence of singletons and descending (resp. ascending) separable permutations
(“blocks”), we obtain the system $\left\\{{A=\frac{(t+D)^{2}}{1-(t+D)}},\ \
{D=\frac{(t+A)^{2}}{1-(t+A)}}\right\\}$. Due to the symmetry $A(t)=D(t)$, we
have $A=\frac{(t+A)^{2}}{1-(t+A)}$. This yields
$F(t)=\frac{1-t-\sqrt{1-6t+t^{2}}}{2}$, the generating function of Schröder
numbers (A006318).

Case 2:  -avoiding guillotine diagonal rectangulations.

######  Lemma 2.

A guillotine diagonal rectangulation $\mathcal{R}$ avoids  if and only if
$\delta(\mathcal{R})$ avoids $2\underline{14}3$.

Proof (sketch). This result follows from the bijection $\delta$ described
above. An occurrence of  in $\mathcal{R}$ means that there are four rectangles
$a,b,c,d$ as in the drawing, where the segment that separates $a$ and $b$ from
$c$ and $d$ is a cut at some step of the recursive decomposition of
$\mathcal{R}$. It follows that in $\delta(\mathcal{R})$ we have

four indices $a<b<c<d$ such that $a$ and $b$ belong to a descending block, and
$c$ and $d$ belong to the next descending block. This yields an occurrence of
$2\underline{14}3$ in $\delta(R)$. The converse direction is based on similar
considerations. ∎

Now we enumerate $2\underline{14}3$-avoiding separable permutations. Let $\pi$
be such a permutation. If $\pi$ is ascending, then it either consists of at
least two singletons, or it has one or several descending blocks, which are
separated by at least one singleton (see the drawing). For descending
permutations the decomposition is identical to Case 1, since the skew sum of
$2\underline{14}3$-avoiding ascending blocks cannot create a new occurrence of
$2\underline{14}3$. This leads to the system

$\left\\{A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}\frac{1}{1-\frac{tD}{1-t}}-1\right)D,\
\ D=\frac{(t+A)^{2}}{1-(t+A)}\right\\}$. Solving this system (for example by
computer algebra) yields Theorem 1(2).

Case 3:  -avoiding guillotine diagonal rectangulations.

First we show that a guillotine diagonal rectangulation $\mathcal{R}$ avoids
if and only if $\delta(\mathcal{R})$ avoids $21354$. As in Lemma 2, the proof
directly follows from the definition of $\delta$.

Thus, we need to enumerate $21354$-avoiding separable permutations. Let $\pi$
be a direct sum of several singletons and $21354$-avoiding descending
separable permutations. If $\pi$ has at most one descending block, then it
avoids $21354$; and if $\pi$ has at least three descending blocks, then it
contains $21354$. If $\pi$ has precisely two descending blocks, then $\pi$ is
$21354$-avoiding if and only if these descending blocks are adjacent; the
first is $213$-avoiding, and the second is $132$-avoiding. In its turn, an
ascending $213$-avoiding permutation is either the identity permutation of
size $\geq 2$, or consists of at least one singleton and precisely one
$213$-avoiding descending block (the last block). Let $S_{A}$ and $S_{D}$ be
generating functions for ascending and, respectively, descending
$213$-avoiding (and, equivalently, $132$-avoiding) permutations. Then, we have
$\left\\{S_{A}=\frac{t^{2}}{1-t}+\frac{tS_{D}}{1-t},\ \
S_{D}=\frac{(t+S_{A})^{2}}{1-(t+S_{A})}\right\\}$, and for $21354$-avoiding
separable permutations we have
$\left\\{{A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)D+\frac{S_{D}^{2}}{(1-t)^{2}}},\
\ {D=\frac{(t+A)^{2}}{1-(t+A)}}\right\\}$. Solving these systems yields
Theorem 1(3).

The treatment of other cases in Theorem 1 is similar. That is, we first
translate geometric patterns into permutation patterns, thus obtaining some
subclass of separable permutations. Then its combinatorial specification
yields a system of equations that binds $A(t)$, the generating functions for
ascending permutations in this class, and $D(t)$ for descending permutations.
In some cases we use an auxiliary family (as in Case 3 above). Here we omit
the details and only list permutation patterns, systems that bind $A(t)$ and
$D(t)$, and, when relevant, auxiliary families and systems for their
generating functions $S_{A}$ and $S_{D}$.

Case 4: $\\{$ , $\\}$-avoiding guillotine diagonal rectangulations. Such
rectangulations are called one-sided guillotine rectangulations [14]. This
family corresponds to $(2\underline{14}3,3\underline{41}2)$-avoiding separable
permutations. Due to the symmetry of the model, we have $A(t)=D(t)$, and,
therefore, just one equation:
${A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}\frac{1}{1-\frac{tA}{1-t}}-1\right)A}$.

Case 5: $\\{$ , $\\}$-avoiding guillotine diagonal rectangulations. They
correspond to $2143$-

avoiding separable permutations, the system is
$\left\\{{A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)D},\ \
{D=\frac{(t+A)^{2}}{1-(t+A)}}\right\\}$.

Case 6: $\\{$ , $\\}$-avoiding guillotine diagonal rectangulations. They
correspond to $(2\underline{14}3,45312)$-avoiding separable permutations. The
auxiliary class is $(2\underline{14}3,231)$-avoiding permutations. The system
for the auxiliary class is
$\left\\{{S_{A}=\frac{t^{2}}{1-t}+\left(\frac{1}{1-\frac{tS_{D}}{1-t}}\frac{1}{(1-t)^{2}}-1\right)S_{D}},\right.$
$\left.{S_{D}=\frac{t^{2}}{1-t}+\frac{tS_{A}}{1-t}}\right\\}$. The system for
$(2\underline{14}3,45312)$-avoiding separable permutations is
$\left\\{{A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}\frac{1}{1-\frac{tD}{1-t}}-1\right)D},\
\
{D=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)A+\frac{S_{A}^{2}}{(1-t)^{2}}}\right\\}$.

Case 7: $\\{$ , , $\\}$-avoiding guillotine diagonal rectangulations. They
correspond to $(21354,45312)$-avoiding separable permutations. The auxiliary
class is $(45312,213)$-avoiding permutations. The system for the auxiliary
class is $\left\\{{S_{A}=\frac{t^{2}}{1-t}+\frac{S_{D}}{1-t}},\ \
S_{D}=\frac{t^{2}}{1-t}+\right.$
$\left.\left(\frac{1}{(1-t)^{2}}-1\right)S_{A}+\left(\frac{1}{1-t}\frac{t^{2}}{1-2t}\right)^{2}\right\\}$.
The equation for $(21354,45312)$-avoiding separable permutations is
${A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)A+\frac{S_{D}^{2}}{(1-t)^{2}}}$.

Case 8: $\\{$ , , $\\}$-avoiding guillotine diagonal rectangulations. They
correspond to $(2143,3\underline{41}2)$-avoiding separable permutations. The
system is
$\left\\{{A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)D},\right.$
$\left.{D=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}\frac{1}{1-\frac{tA}{1-t}}-1\right)A}\right\\}$.

Case 9: $\\{$ , , $\\}$-avoiding guillotine diagonal rectangulations. They
correspond to $(2143,45312)$-avoiding separable permutations. The auxiliary
class is $(2143,231)$-avoiding permutations. The system for the auxiliary
class is
$\left\\{{S_{A}=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)S_{D}},\ \
S_{D}=\right.$ $\left.\frac{t^{2}}{1-t}+\frac{tS_{A}}{1-t}\right\\}$. The
system for $(2143,45312)$-avoiding separable permutations is
$\left\\{A=\frac{t^{2}}{1-t}+\right.$
$\left.\left(\frac{1}{(1-t)^{2}}-1\right)D,\ \
{D=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)A+\frac{S_{A}^{2}}{(1-t)^{2}}}\right\\}$.

Case 10: $\\{$ , , , $\\}$-avoiding guillotine diagonal rectangulations. They
correspond to $(2143,3412)$-avoiding separable permutations. The equation for
this symmetric model is
${A=\frac{t^{2}}{1-t}+\left(\frac{1}{(1-t)^{2}}-1\right)A}$.

##  4 Vortex rectangulations and whirls

In this section we consider a class harder to enumerate, as it is not a
guillotine case: rectangulations that avoid $\\{$ $\\}$ (that is, we forbid
all our patterns except $P_{2}=$ ). We denote this class of rectangulations by
$\mathcal{V}$, and call them vortex rectangulations. Our ultimate goal is to
prove the following conjecture by Merino and Mütze [16].

######  Theorem 3.

The generating function of $\mathcal{V}$ is $V(t)=tC^{2}(t)(1+t^{2}C^{4}(t))$,
where $C(t)=\frac{1-\sqrt{1-4t}}{2t}$ is the generating function of Catalan
numbers. The enumerating sequence of $\mathcal{V}$ is A026029.

A vortex either avoids or contains the pattern $P_{2}=$ . Vortices that avoid
constitute Case 10 from Theorem 1. It remains to enumerate vortices with at
least one  : such rectangulations will be called whirls. The interior of a
windmill is the (possibly further partitioned) rectangular area bounded by its
segments. The entire rectangle being partitioned by a given rectangulation
will be denoted by $R$.

######  Lemma 4.

If a whirl contains several windmills, then they are all nested. In other
words: for any two windmills, one of them entirely lies in the interior of the
other.

###### Proof (sketch)..

Let $W$ be a whirl, and consider some specific occurrence of  . Starting from
the right vertical segment of this windmill, we alternately go along the
segments downwards to their lower endpoint and rightwards to their right
endpoint, until we reach the SE corner of $R$. Similarly we define four
alternating paths: see Figure 2 where they are shown by red.

These alternating paths partition $R$ into five areas: $R_{1}$, $R_{2}$,
$R_{3}$, $R_{4}$, and the interior of the windmill. In our drawings we color
these areas by blue, red, yellow, green, and grey. Then every rectangle in
$R_{1}$ and in $R_{3}$ has its top and bottom sides on the alternating paths,
and every rectangle in $R_{2}$ and in $R_{4}$ has its left and right sides on
the alternating paths (see Figure 2). To prove this, for example for $R_{1}$,
one scans this area from the left to the right: then the assumption that some
rectangle in $R_{1}$ violates this condition leads to an occurrence of ,  or .
Moreover, for every rectangle in $R_{1}$ its NW corner has the shape  and its
SW corner has the shape . It follows that if another windmill — not in the
interior of the given one — exists, then its segments belong to four different
areas $R_{1}$, $R_{2}$, $R_{3}$, $R_{4}$. Hence, the given windmill is
entirely included in this another one. ∎

A whirl with an empty interior can be drawn in such a way that all the
rectangles in $R_{1}$ and $R_{3}$ have width $1$, and all the rectangles in
$R_{2}$ and $R_{4}$ have height $1$ (such a representation is unique). See
Figure 2(a) for an example of a whirl which has two nested windmills (the
corners of their interiors are shown by small dots).

Figure 2: Three whirls: (a) is peelable, (b) is non-peelable, (c) is simple.

A whirl is peelable if it has a rectangle that extends from the top to the
bottom or from the left to the right side of $R$. From every peelable whirl it
is possible to obtain a unique non-peelable whirl by peeling (i.e.,
successively deleting such rectangles). Figure 2(b) shows a non-peelable whirl
which is obtained from 2(a) by peeling.

Finally, a simple whirl is a non-peelable whirl with precisely one windmill
whose interior is not further partitioned. See Figure 2(c) for an example of a
simple whirl.

###  4.1 Enumeration of simple whirls

In this section we prove the following remarkable result: simple whirls are
enumerated by $t^{5}C^{4}(t)$. Our proof combines geometric-structural
considerations, the generating tree method [5], and solving a functional
equation with catalytic variables. It would be interesting to find an
independent bijective proof.

####  4.1.1 Generating tree

Denote by $S_{1},S_{2},S_{3},S_{4}$ the eastern, southern, western, northern
sides of $R$. A signature of a simple whirl is the quadruple
$(a_{1},a_{2},a_{3},a_{4})$, where the component $a_{i}$ is the number of
rectangles from $R_{i-1}$ that touch $S_{i}$. (The addition of indices of
$R_{i}$’s and $S_{i}$’s is $\mathrm{mod}\ 4$.) For example, the signature of
the simple whirl from Figure 2(c) is $(3,2,1,2)$.

For every $i=1,2,3,4$, there is precisely one exterior rectangle that belongs
to $R_{i}$ and has a (“long”) side included in $S_{i}$ and a (“short”) side
included in $S_{i+1}$. (If we assume that this condition is violated, we
obtain either a forbidden pattern or a peelable whirl.) Given a simple whirl
$W$, we can construct another simple whirl $W^{\prime}$ by adding a new
exterior rectangle of $R_{i}$ that would completely cover the exterior
rectangle of $R_{i}$ in $W$ and possibly extend more towards the side
$S_{i-1}$ (but not reach it). Some rectangles of $R_{i-1}$ will be then
extended to reach the modified $S_{i}$. In $W^{\prime}$, $a_{i+1}$ increases
by $1$, and $a_{i}$ can assume all the values from $1$ to the (original)
$a_{i}$. This generation algorithm has the drawback that some simple whirls
are generated several times.

To generate every simple whirl precisely once, we consider only those
possibilities in which the added exterior rectangle of $W^{\prime}$ belongs to
$R_{i}$ with the largest possible $i$ (that is, the largest $i$ such that in
$W^{\prime}$ we have $a_{i+1}>1$). To obtain this, one starts from the initial
configuration $(1,1,1,1)$ (only the unique simple whirl of size $5$ has this
signature), and applies the following rewriting rules

$\begin{array}[]{lcccl}\text{1.}\ (a,\ b,\ 1,\ 1)\ \longrightarrow\ (1,\ b+1,\
1,\ 1),&&&&\text{3.}\ (1,\ b,\ c,\ d)\ \longrightarrow\ (1,\ b,\ [1..c],\
d+1),\\\ \text{2.}\ (1,\ b,\ c,\ 1)\ \longrightarrow\ (1,\ [1..b],\ c+1,\
1),&&&&\text{4.}\ (a,\ b,\ c,\ d)\ \longrightarrow\ (a+1,\ b,\ c,\
[1..d]).\end{array}$

The notation $[1..b]$ means that we generate $b$ signatures where this
component takes the values $1,2,\ldots,b$. The rules are not mutually
exclusive: for example, all four rules can be applied on quadruples of the
form $(1,b,1,1)$. The figure below shows all the descendants of a simple whirl
$W$ with signature $(1,2,3,1)$ on which the second, the third, and the fourth
rules can be applied. The first rule does not apply since the resulting whirl
$W^{\prime}$ is obtained from a whirl different from $W$. New exterior
rectangles are shown by bold boundary.

####  4.1.2 An intriguing functional functional equation

######  Theorem 5 (Algebraicity of simple whirls).

Let $F(t,x_{1},x_{2},x_{3},x_{4})$ be the multivariate generating function of
simple whirls, where $z$ counts their size, and each $x_{i}$ counts the number
of rectangles of color $i$ touching their border. This generating function is
algebraic and given by the closed form

$F(t,x_{1},x_{2},x_{3},x_{4})=t^{5}\frac{1}{2\alpha}\left(\beta-\sqrt{\beta^{2}-4\alpha
e_{4}^{2}}\right)$ (1)

with $\alpha:=\prod_{i=1}^{4}(1-x_{i}+tx_{i}^{2})$ and
$\beta:=(2e_{4}t^{2}-4t(e_{4}-3e_{3}+2e_{2})+e_{4}-e_{3}+e_{2}-e_{1}+2)e_{4}$,
where $e_{m}:=[t^{m}]\prod_{i=1}^{4}(1+tx_{i})$ is the elementary symmetric
polynomial of total degree $m$.

In particular, the generating function of simple whirls is
$F(t)=F(t,1,1,1,1)=t^{5}C(t)^{4}$, where $C(t)$ is the generating function of
Catalan numbers.

###### Proof.

The generating tree from Section 4.1.1 translates to the functional equation

$\displaystyle\begin{split}&F(t,x_{1},x_{2},x_{3},x_{4})=t^{5}x_{1}x_{2}x_{3}x_{4}+tx_{1}x_{2}x_{3}x_{4}[x_{3}x_{4}]F(t,1,x_{2},x_{3},x_{4})\\\
&+tx_{1}x_{3}x_{4}\frac{[x_{1}x_{4}]F(t,x_{1},x_{2},x_{3},x_{4})-x_{2}[x_{1}x_{4}]F(t,x_{1},1,x_{3},x_{4})}{x_{2}-1}\\\
&+tx_{1}x_{4}\frac{[x_{1}]F(t,x_{1},x_{2},x_{3},x_{4})-x_{3}[x_{1}]F(t,x_{1},x_{2},1,x_{4})}{x_{3}-1}\\\
&+tx_{1}\frac{F(t,x_{1},x_{2},x_{3},x_{4})-x_{4}F(t,x_{1},x_{2},x_{3},1)}{x_{4}-1}.\end{split}$
(2)

Unfortunately, there are currently no generic methods to solve this type of
catalytic functional equation. Luckily, in our case, we were able to solve
this equation; we invite the readers to give it a try before going on with
their reading!

Here is how we solved it. First, recall that the valuation of a series
$f(t)=\sum_{n\geq 0}f_{n}t^{n}$ isthe smallest integer $n$ such that
$f_{n}\neq 0$ (and $\operatorname{val}(f(t))=+\infty$ if $f(t)=0$). Thus,
Equation (2)is a contraction in the metric space of formal power series
(equipped with the distance
$d(f(t),g(t))=2^{-\operatorname{val}(f(t)-g(t))}$). Therefore, the Brouwer
fixed-point theorem ensures thatthere is a unique series $F$ satisfying
Equation (2). Now, it can be checked (by substitution) that the closed form
(1) satisfies the functional equation (2); this proves the theorem.

Let us also explain how we guessed this closed form, as it offers a useful
heuristic for dealing with similar equations. The classical guessing technique
using Padé approximants is too costly, so, instead, we used linear algebra to
identify an algebraic equation of degree 2 (in $F$) and degree 8 (in $x_{1}$)
for $F(t,x_{1},11,31,71)$. It is not obvious from the functional equation that
$F(t,x_{1},x_{2},x_{3},x_{4})$ is a symmetric function in the $x_{i}$’s — yet,
this follows from the fact that any rotation of a whirl is still a whirl.
Therefore, its minimal polynomial should also have symmetric coefficients in
the $x_{i}$’s. Then, when one obtains a monomial like
$532642x_{1}=2x_{1}\times 11^{2}\times 31\times 71$, it makes sense to rewrite
it as $2x_{1}x_{2}^{2}x_{3}x_{4}$, and all the symmetric versions of this
monomial will also appear as coefficients. This leads to the minimal
polynomial $\alpha F^{2}-\beta F+e_{2}^{4}$, the solution of which gives the
closed form (1). ∎

###  4.2 Enumeration of whirls and vortices

We go back from simple whirls to possibly peelable whirls with empty interior
by alternately adding sequences of rectangles on the two horizontal and the
two vertical sides. This yields the generating function
$P(t)=t^{5}C^{4}(t)\left(\frac{2}{1-\left(\frac{1}{(1-t)^{2}}-1\right)}-1\right).$

Such whirls can be transformed into a whirl with $>1$ windmills by
substituting the interior by another whirl (see Figure 2). Therefore, whirls
$\mathcal{W}$ with empty interior of the innermost windmill are enumerated as
a sequence of $P(t)/t$. Thus we obtain the generating function
$W(t)=\frac{1}{1-P(t)/t}$.

Finally, to get the family $\mathcal{V}$ of vortices (i.e. the rectangulations
that avoid  , , , , , , ), we replace the innermost windmill by a
rectangulation that avoids all eight patterns (i.e., Case 10 from Theorem 1,
counted by $Z(t)=\frac{t(1-2t)}{1-4t+2t^{2}}$). This leads to

$V(t)=W(t)Z(t)=\frac{(1-2t)\big{(}\,1-4t+2t^{2}+(1-2t)\sqrt{1-4t}\,\big{)}}{2t^{3}}=tC^{2}(t)(1+t^{2}C^{4}(t)),$

which is exactly the generating function of the sequence A026029, as
conjectured in [16, Table 3, entry 1345678]. This concludes the proof of
Theorem 3.

Note that, like for any algebraic generating function [6], the corresponding
sequence satisfies a linear recurrence,
$(n+4)v_{n}-6(n+2)v_{n-1}+4(2n-1)v_{n-2}=0$, from which one can compute
$v_{n}$ in time $O(\sqrt{n}\ln n)$, and singularity analysis [15] gives
$v_{n}\sim 4^{n+2}/\sqrt{\pi}n^{-3/2}$.

##  5 Conclusion

In this article, we solved several conjectures related to families of pattern-
avoiding rectangulations and permutations. We proved that all our generating
functions are $\mathbb{N}$-algebraic222This is the class of generating
functions counting words of length $n$ generated by unambiguous context-free
grammars. It has many noteworthy structural and asymptotic properties [6, 9,
11]., and we provide an interesting example of $\mathbb{N}$-algebraic
structure (the simple whirls, counted by $t^{5}C^{4}(t)$) for which no
context-free grammar is known.

Merino and Mütze [16, Table 3] are mentioning a few more families of
rectangulations for which the enumeration is still open. Some of them are in
fact tractable with variants of methods presented in our article. These
results will be included in the long version of our article. It would also be
of interest to consider further forbidden patterns, e.g., to determine which
patterns lead to algebraic, D-finite, D-algebraic generating functions. Also,
is it the case that they all lead to a Stanley–Wilf-like conjecture: is the
number of such rectangulations bounded by $A^{n}$, for some constant $A$?

In conclusion, the rectangulations, while having a very simple definition, are
an inexhaustible source of challenging problems for generating function
lovers!

## References

  * [1] Eyal Ackerman, Gill Barequet, and Ron Y. Pinter.  A bijection between permutations and floorplans, and its applications.  Discrete Appl. Math., 154(12):1674–1684, 2006.
  * [2] Andrei Asinowski, Gill Barequet, Mireille Bousquet-Mélou, Toufik Mansour, and Ron Y. Pinter.  Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations.  Electron. J. Comb., 20(2):article p35, 43 pp., 2013.
  * [3] Andrei Asinowski, Jean Cardinal, Stefan Felsner, and Éric Fusy.  Combinatorics of rectangulations: Old and new bijections.  In preparation.
  * [4] Andrei Asinowski and Toufik Mansour.  Separable $d$-permutations and guillotine partitions.  Ann. Comb., 14(1):17–43, 2010.
  * [5] Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy, and Dominique Gouyou-Beauchamps.  Generating functions for generating trees.  Discrete Math., 246(1-3):29–55, 2002.
  * [6] Cyril Banderier and Michael Drmota.  Formulae and asymptotics for coefficients of algebraic functions.  Comb. Probab. Comput., 24(1):1–53, 2015.
  * [7] Miklós Bóna.  Combinatorics of permutations.  CRC Press, 3rd edition edition, 2022.
  * [8] Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw.  Pattern matching for permutations.  Information Processing Letters, 65(5):277–283, 1998.
  * [9] Mireille Bousquet-Mélou.  Rational and algebraic series in combinatorial enumeration.  In Proceedings of the International Congress of Mathematicians, Madrid, August 22–30, 2006. Volume III: Invited lectures, pp. 789–826. European Mathematical Society, 2006.
  * [10] Jean Cardinal, Vera Sacristán, and Rodrigo I. Silveira.  A note on flips in diagonal rectangulations.  Discrete Math. Theor. Comput. Sci., 20(2):22, 2018.  Id/No 14.
  * [11] Noam Chomsky and Marcel-Paul Schützenberger.  The algebraic theory of context-free languages.  In Computer Programming and Formal Systems, pp. 118–161. Elsevier, 1963.
  * [12] Fan Rong K. Chung, Ronald L. Graham, Verner E. Hoggatt, and Mark Kleiman.  The number of Baxter permutations.  J. Comb. Theory, Ser. A, 24:382–394, 1978.
  * [13] David Eppstein, Elena Mumford, Bettina Speckmann, and Kevin Verbeek.  Area-universal and constrained rectangular layouts.  SIAM J. Comput., 41(3):537–564, 2012.
  * [14] Stefan Felsner, Andrew Nathenson, and Csaba D. Tóth.  Aspect ratio universal rectangular layouts.  Proc. of Walcom 22, LNCS 13174, pp. 73–84, 2022.
  * [15] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [16] Arturo Merino and Torsten Mütze.  Combinatorial generation via permutation languages. III. Rectangulations.  Discrete Comput. Geom., 70:51–122, 2023.
  * [17] William John Mitchell, John Philip Steadman, and Robin Segerblom Liggett.  Synthesis and optimization of small rectangular floor plans.  Environment and Planning B: Planning and Design, 3(1):37–70, 1976.
  * [18] Nathan Reading.  Generic rectangulations.  Eur. J. Comb., 33(4):610–623, 2012.
  * [19] John Philip Steadman.  Architectural Morphology.  Pion, 1983.